Shellsort
Time complexity: about O(n^1.3).
Result
Examples
How it works
Shellsort runs insertion sort on items far apart first, then closer and closer, ending with a normal insertion sort on a list that is already nearly sorted.
When to use it
Small embedded systems, where a simple in-place sort must be much faster than O(n²).