# Tag Info

3

qsort is not Quicksort. qsort is whatever the implementor of the standard library decided. Sorting 50 million identical values is highly unrepresentative. There are qsort implementations that will sort 50 million identical, or 50 million sorted or reverse sorted elements in linear time. Radix sort of 50 million numbers with six digits is obviously nonsense....

1

For the sake of avoiding dealing with rounding in the analysis, assume for simplicity that $k$ is a power of $2$ (if it is not, you can add $d \le k-1$ dummy arrays with one $+\infty$ element each, and ignore the last $d$ elements in the final sorted vector). You can merge your arrays two by two in a binary-tree fashion: the algorithm works in $\log k$ ...

1

Quicksort and mergesort can both be implemented to work directly on a linked list with just $O(1)$ extra space. This actually improves the space complexity of the usual mergesort, which ordinarily requires $O(n)$ working space (this is because the pointers actually constitute $O(n)$ extra space themselves). As usual, mergesort will take $O(n\log n)$ time in ...

Only top voted, non community-wiki answers of a minimum length are eligible