Nested sorting class of array sorting algorithms

[Paul Dale]

I think this will fall out as O(n log n) time and O(n) storage. However, the constant terms will be large. The temporary buffers in the merge phase guarantee two copies for every item for every merge. For the final merge of two half lists, it requires O(n) storage. On the other hand, quicksort requires O(log n) additional storage and takes O(n log n) time on average. It also doesn't double copy.

The sorting wars were essentially resolved in the 1970s. There are some interesting parallel sorts but my favourite is this one.

If you've not watched these before, have fun.


Pauli