Effective functional sorting

Question

I am programming a function for TI-Nspire , so I cannot use the built-in functions inside the function. What is the most general algorithm for sorting a list of numbers without changing the list itself? (recursion and splitting lists are fair play, as is the general use of mathematics.)

Answer 1

Mergesort is simple, simple, efficient, and stable: splits a list, sorts recursively, and combines results.

To be more specific, mergesort accepts O (N log N), which is asymptotically optimal. In addition, in practice (using both algorithms modified to sort short sublists with a special type), mergesort can be a close competitor to the modified quick sort used in standard C / C ++ libraries.

Edit: unlike in-place sorts, such as quicksort and insertion sorting, mergesort requires auxiliary memory and is easiest to implement by copying rather than swapping.

Answer 2

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

, ,