New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
sort: add SortStable #3671
Labels
Comments
That's a pretty significant change. Usually a better way is for the caller to put an index into each element being sorted to be used to break ties. Package sort could build a wrapper to do this but it would be far less efficient - would have to allocate a new slice as big as the input just to hold the original indices. Russ |
Right now, sort.Sort provides an in-place, comparison-based sort that runs in additional logarithmic memory (just the stack space for the recursive calls). I am unaware of any practical stable, in-place, comparison-based sorts that do not require additional linear memory (to track where things were originally). If someone does know, please tell us. Russ |
I'm not sure it belongs in package sort, but here's code that I imagine would work. type stable struct { x sort.Interface perm []int } func (s *stable) Len() int { return len(s.perm) } func (s *stable) Less(i, j int) bool { return s.x.Less(i, j) || !s.x.Less(j, i) && s.x.perm[i] < s.x.perm[j] } func (s *stable) Swap(i, j int) { s.x.Swap(i, j) s.perm[i], s.perm[j] = s.perm[j], s.perm[i] } func Stable(x sort.Interface) sort.Interface { s := &stable{ x: x, perm: make([]int, x.Len()), } for i := range s.perm { s.perm[i] = i } return s } sort.Sort(x) => sort.Sort(Stable(x)) |
I did some experiments with the following inplace merge sort algorithms: - gcc-4.6.3's __inplace_stable_sort [1] - SymMerge from Kim and Kutzner [2] - SplitMerge, also from Kim and Kutzner [3] All three algorithms seem to work (they sort and are stable) but the Sym- and Split-merge algorithms seem to be significantly faster than gcc's variant. Funny enough, they are also faster than quicksort/ heapsort combination from package sort. (Actually this gives me no real confidence in my three implementations). BenchmarkSortInt1K 5000 614815 ns/op BenchmarkSymMergeSortInt1K 10000 188012 ns/op BenchmarkSplitMergeSortInt1K 10000 204298 ns/op BenchmarkInplaceStableSortInt1K 5000 652065 ns/op BenchmarkSortInt64K 50 56432255 ns/op BenchmarkSymMergeSortInt64K 100 15533944 ns/op BenchmarkSplitMergeSortInt64K 100 15890060 ns/op BenchmarkInplaceStableSortInt64K 50 53262765 ns/op BenchmarkSortInt4096K 1 4948032225 ns/op BenchmarkSymMergeSortInt4096K 1 1211093742 ns/op BenchmarkSplitMergeSortInt4096K 1 1248584376 ns/op BenchmarkInplaceStableSortInt4096K 1 3893523171 ns/op BenchmarkSymMergeSorted4096k 5 354807619 ns/op BenchmarkSplitMergeSorted4096k 5 399972589 ns/op BenchmarkInplaceStableSorted4096k 1 1005064702 ns/op BenchmarkSymMergeReversed4096k 1 2171833903 ns/op BenchmarkSplitMergeReversed4096k 1 2203106583 ns/op BenchmarkInplaceSortReversed4096k 1 6184138377 ns/op I could drop the current state into a CL which might encourage others to play with the algorithms. The whole code for SymMerge is just 110 lines with 50 lines a fancy version of rotate. Any comments? [1] http://gcc.gnu.org/onlinedocs/gcc-4.6.3/libstdc++/api/a01045_source.html#l03454 [2] Pok-Son Kim, Arne Kutzner: Stable Minimum Storage Merging by Symmetric Comparisons [3] Pok-Son Kim, Arne Kutzner: A Simple Algorithm for Stable Minimum Storage Merging |
bradfitz
added
fixed
Suggested
Issues that may be good for new contributors looking for work to do.
labels
Jul 30, 2013
This issue was closed.
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
Labels
The text was updated successfully, but these errors were encountered: