Content deleted Content added
Line 112:
::What the original source cares about (and what I sloppily summarized as "no benefit") is the exact expected number of comparisons, not the big-O complexity. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 15:22, 7 December 2015 (UTC)
:::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:
| |||