sort: add SortStable

[bradfitz]

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]

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]

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]

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]

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]

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]

Comment 6:

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

Status changed to Thinking.

[bradfitz]

Comment 7:

Labels changed: added suggested.

[vdobler]

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]

Comment 9:

sort.Stable is in

Status changed to Fixed.