Skip to content
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

Closed
bradfitz opened this issue May 25, 2012 · 9 comments
Closed

sort: add SortStable #3671

bradfitz opened this issue May 25, 2012 · 9 comments

Comments

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented May 25, 2012

I just did a code review where the author couldn't use sort.Sort because they needed a
stable sort.

Maybe we could add SortStable(data Interface) to pkg sort?
@rsc
Copy link
Contributor

@rsc rsc commented May 25, 2012

Comment 1:

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
@rsc
Copy link
Contributor

@rsc rsc commented May 25, 2012

Comment 2:

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
@bradfitz
Copy link
Contributor Author

@bradfitz bradfitz commented May 25, 2012

Comment 3:

In this case the author was sorting a slice of protos from another team, so adding a new
field to the struct wasn't a practical option.
The wrapper in package sort could document its inefficiency and the alternative?
@rsc
Copy link
Contributor

@rsc rsc commented May 25, 2012

Comment 4:

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))
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented May 25, 2012

Comment 5:

Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996) Practical in-place mergesort.
Takes an additional O(N) comparisons, so it couldn't be a replacement for sort.Sort,
just an alternative.
That's the algorithm that libstdc++ uses for std::stable_sort.
@robpike
Copy link
Contributor

@robpike robpike commented Jun 1, 2012

Comment 6:

Labels changed: added priority-later, removed priority-triage.

Status changed to Thinking.

@bradfitz
Copy link
Contributor Author

@bradfitz bradfitz commented Mar 28, 2013

Comment 7:

Labels changed: added suggested.

@vdobler
Copy link
Contributor

@vdobler vdobler commented May 16, 2013

Comment 8:

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
@rsc
Copy link
Contributor

@rsc rsc commented Jul 30, 2013

Comment 9:

sort.Stable is in

Status changed to Fixed.

@golang golang locked and limited conversation to collaborators Jun 24, 2016
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.