Content deleted Content added
Line 113:
:::The number of moves is also a factor, but the total number of operations remains the same, k=2, n log2(n) compares + n log2(n) moves = 2 n log2(n) total operations. k=4, 1 1/2 n log2(n) compares + 1/2 n log2(n) moves = 2 n log2(n) total operations. On my system, Intel 2600K 3.4ghz, in 64 bit mode (16 registers), a 4 way merge sort of psuedo random 64 bit unsigned integers is about 12% to 15% depending on the number of integers (12% for 4 million, 15% for 64 million). The 4 way merge sort on integers is about as fast as quick sort. The relative performance is affected by the overhead of compares versus the overhead of moves. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 18:28, 7 December 2015 (UTC)
* Computational complexity is not about efficient use of registers on a particular machine. Furthermore, comparisons are usually not simple integer operations even though books on algorithms use that for clarity. [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 04:24, 9 December 2015 (UTC)
| |||