Re: Natural sort comparison
- Posted by Spock Aug 13, 2017
- 1878 views
I found a way to improve quick_sort for the all-1s case, along with a minor speedup for the swap: .... Which makes it the clear winner across the board in my "Compare_sorting_algorithms.exw".
Given the performance boost that qstack gives to quick_sort, I wonder whether a similar technique could be applied to merge_sort, likewise turning it from a recursive algorithm to an iterative one, and whether merges could be performed in-situ. I jotted down some outline thoughts...
Pete
Your enhanced Quick sort is definitely faster (but won't be stable). I had already started some work on an in-place Merge sort but got a bit distracted looking at Library sort (gapped Insertion sort) which might be better than Merge sort in some ways. It is like a Bucket sort which clumps values into discrete sorted groups. I want to try something along the same lines but leave the final sort till the end. If each [unsorted] clump were kept under a minimum size (you suggest n=64) Insertion sort would be the ideal final pass.
Spock
