Effective functional sort

I'm programming a function for a TI-Nspire, so I can't use the builtins from inside 开发者_StackOverflow社区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.)

---

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.

---

Timsort is used in python and java SE 7. It takes the best of merge sort and insertion sort. Insertion sort is O(n^2) but with small lists of numbers it is faster than merge sort!

So you can use this as a generic sorting algorithm as stated here