Re: Natural sort comparison
- Posted by Spock Jul 23, 2017
- 2070 views
Am I right in thinking that the existing sort is perfectly stable - what is not stable is custom_sort, because you don't get any indexes with which to resolve ties.
"custom_sort" happens to lack an option for choice of columns
If you have just one column then all sorting algorithms give you the same answer. If items get swapped or not, you can not tell. Stability does not matter.
When you have two (or more columns) and you sort using a column a the key, then you can tell the difference. Stable sorting becomes important.
Using Andy's natural sort order: I got the same result with Mike_sort and std/sort.e; the items have no columns but have an "internal" order.
_tom
It's not necessary for custom_sort to pass any column ordering since the User's compare routine would take this into account. Except for sorting one-dimensional data the choice of algorithm will impact stability. Indexes can be used to convert any unstable sort into a stable one but I think it's easier to just use a naturally stable sort in the first place. Please correct me if I'm wrong but AFAIK the existing sort in \std is based on Shell sort so not stable.
Msort is basically Merge sort supplemented by Insertion sort. This is more-or-less the core of Timsort (I personally think Tim Peters went way overboard trying to squeeze out every last drop of performance). In my own tests Msort easily beats Qsort in any use case. It's fast and always correct so please feel free to use it how you want.
Spock
