Effective functional sort

Question

I'm programming a function for a TI-Nspire, so I can't use the builtins from inside a function. What is the most generally efficient algorithm for sorting a list of numbers without modifying the list itself? (recursion and list-splitting are fair game, as is general use of math.)

Answer 1

Mergesort is straightforward, simple, efficient, and stable: split the list, sort recursively, and merge the results.

To be more specific, mergesort takes O(N log N), which is asymptotically optimal. Also, in practice (with both algorithms modified to sort short sublists with a special-purpose sort), mergesort can be a close competitor to the modified quicksort used in the C/C++ standard libraries.

Edit: unlike in-place sorts like quicksort and insertion sort, mergesort requires auxiliary memory, and is simplest to implement by copying rather than swapping.