Content deleted Content added
Removed bullshit reference to paper that claims to solve a problem with linear output size in sub-linear running time. Tag: references removed |
|||
Line 89:
The value 2 is repopulated by the next value in the sorted list, 19. The comparisons end with 5 being the smallest value, and thus the next value to be popped off. This continues until all of the sorted lists are empty.
==== Lower Running Time Bound ====
One can show that no comparison-based K-Way Merge algorithm exists with a running time in O(n f(k)) where f grows asymptotically slower than a logarithm.
The proof is a straight forward reduction from comparison-based sorting.
Suppose that such an algorithm existed, then we can construct a comparison-based sorting algorithm with running time O(n f(n)) as follows:
Chop the input array n into n arrays of size 1.
Merge these n arrays with the K-Way Merge algorithm.
The resulting array is sorted and the algorithm has a running time in O(n f(n)).
This is a contradiction to the well-known result that no comparison-based sorting algorithm with a worst case running time below O(n log n) exists.
== External Sorting<ref>{{Cite book|title = Data Structures and Algorithm Analysis in C++, Third Edition|url = https://books.google.com/books?id=AijEAgAAQBAJ|publisher = Courier Corporation|date = 2012-07-26|isbn = 9780486172620|first = Clifford A.|last = Shaffer}}</ref> ==
| |||