Quote:Original post by tsukinokaze
I'm no sorting pro, so it's just a suggestion made from theory not praxis.

If it's almost sorted, how about gnome sort isn't that fast for those types of tasks?

Algorithm:       Comparisons:   Item Assignments:Insertion Sort   4950           5049Gnome Sort       9900           9900

Quote:Original post by iMalc
Gnome Sort operates very much like Insertion Sort, except that it involves repeated swapping instead of what I would call a rotate, and it performs more comparisons because it often ignores much of what it has already determined to be sorted.

Quote:Original post by Inmate2993
If you pass on the std::list solution, I would recommend a Merge sort, as it's fairly easy to implement. One note to make, however, is that you'll probably have to sap up some memory for the arrays needed for Merge, and the two additional O(n) operations copying the list to an array, and then creating a list from the sorted array.