Implement a sorting algorithm.

[ta0kira]

Ideally, stable with worst-case O(n log n) performance and O(1) memory. The memory requirement is flexible, since no deep copies will be made.

[ta0kira]

Actually, I think O(1) storage takes priority over stability, since buffers of arbitrary size aren't a part of the base.

• Block sort meets the original requirement, except that it's extremely complicated, and likely has a high constant. (It also uses bitwise operations, so technically the O(1) depends on the container size being bounded by Int.)
• Smoothsort might be a good option for non-stable sorting, but it seems a bit complicated.
• Heapsort seems like a good compromise for the first attempt.
• This table of sorting algorithms mentions Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves, but it doesn't seem to be available for free anywhere.

[ta0kira]

I guess this really needs to be in lib/container anyway, since lib/util doesn't have a mutable random-access container.