Content deleted Content added
Line 109:
*To clarify - a k-way in memory merge sort (using min-heap, recursion, or something similar to reduce k-1 compares to log2(k) compares), has the same time complexity as a 2-way merge. For n = power of k, then complexity = n logk(n) log2(k) = n log2(n), same as 2 way regardless of k. However the statement is ''no benefit'' as opposed to ''same time complexity''. Even with simple k-1 compare logic (3 compares per move), a 4 way merge sort of integers ends up being slightly faster than a 2 way merge sort, at least in the case of a PC in 64 bit mode (16 registers). The situation would probably be reversed if sorting an array of pointers to objects, since the compare overhead would be greater than the move overhead. The other issue is that a statement about the sort complexity belongs in the sort articles, instead of a merge article. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 13:36, 7 December 2015 (UTC)
::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)
| |||