Implementing and improving a sorting routine

Code up a sorting algorithm of your choice, analyse its running time and memory use, and then suggest improvements.

A good choice is quicksort: average $O(n\log n)$ time, $O(\log n)$ stack, but $O(n^2)$ worst case. Partition around a pivot and recurse on both sides. Improve with median-of-three or random pivots, three-way partitioning for duplicates, insertion sort on small subarrays, recursing on the smaller side first, and falling back to heapsort when depth grows (introsort). Merge sort guarantees $O(n\log n)$ and stability at the price of $O(n)$ extra memory.