Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(37)

Issue 9612044: code review 9612044: sort: provide different stable sort algorithms (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
9 years, 1 month ago by volker.dobler
Modified:
7 years, 11 months ago
Reviewers:
dfc, rsc
CC:
golang-dev, bradfitz, iant, 0xjnml, rsc
Visibility:
Public.

Description

sort: implement stable sorting This CL provides stable in-place sorting by use of bottom up merge sort with in-place merging done by the SymMerge algorithm from P.-S. Kim and A. Kutzner. The additional space needed for stable sorting (in the form of stack space) is logarithmic in the inputs size n. Number of calls to Less and Swap grow like O(n * log n) and O(n * log n * log n): Stable sorting random data uses significantly more calls to Swap than the unstable quicksort implementation (5 times more on n=100, 10 times more on n=1e4 and 23 times more on n=1e8). The number of calls to Less is practically the same for Sort and Stable. Stable sorting 1 million random integers takes 5 times longer than using Sort. BenchmarkSortString1K 50000 328662 ns/op BenchmarkStableString1K 50000 380231 ns/op 1.15 slower BenchmarkSortInt1K 50000 157336 ns/op BenchmarkStableInt1K 50000 191167 ns/op 1.22 slower BenchmarkSortInt64K 1000 14466297 ns/op BenchmarkStableInt64K 500 16190266 ns/op 1.12 slower BenchmarkSort1e2 200000 64923 ns/op BenchmarkStable1e2 50000 167128 ns/op 2.57 slower BenchmarkSort1e4 1000 14540613 ns/op BenchmarkStable1e4 100 58117289 ns/op 4.00 slower BenchmarkSort1e6 5 2429631508 ns/op BenchmarkStable1e6 1 12077036952 ns/op 4.97 slower

Patch Set 1 #

Patch Set 2 : diff -r ccf485b509ff https://code.google.com/p/go/ #

Patch Set 3 : diff -r ccf485b509ff https://code.google.com/p/go/ #

Patch Set 4 : diff -r ccf485b509ff https://code.google.com/p/go/ #

Patch Set 5 : diff -r ca166884c853 https://code.google.com/p/go/ #

Patch Set 6 : diff -r ca166884c853 https://code.google.com/p/go/ #

Patch Set 7 : diff -r ca166884c853 https://code.google.com/p/go/ #

Patch Set 8 : diff -r 41702da0dcc4 https://code.google.com/p/go/ #

Patch Set 9 : diff -r 63b01ec901a6 https://code.google.com/p/go/ #

Patch Set 10 : diff -r 24deeb374803 https://code.google.com/p/go/ #

Total comments: 6

Patch Set 11 : diff -r 41134e67106d https://code.google.com/p/go/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+381 lines, -4 lines) Patch
M src/pkg/sort/sort.go View 1 2 3 4 5 6 7 8 9 10 1 chunk +189 lines, -0 lines 0 comments Download
M src/pkg/sort/sort_test.go View 1 2 3 4 5 6 7 8 9 10 7 chunks +192 lines, -4 lines 0 comments Download

Messages

Total messages: 17
volker.dobler
Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go/
9 years, 1 month ago (2013-05-21 09:09:14 UTC) #1
volker.dobler
Please do not focus on the details like comments or separators, variable names (taken from ...
9 years, 1 month ago (2013-05-21 09:15:29 UTC) #2
bradfitz
Excellent, thanks for working on this! I'm worried about GPL infection. Could you compare stl_algo.h ...
9 years, 1 month ago (2013-05-21 15:31:19 UTC) #3
iant
On Tue, May 21, 2013 at 8:31 AM, Brad Fitzpatrick <bradfitz@golang.org> wrote: > > I'm ...
9 years, 1 month ago (2013-05-21 16:54:08 UTC) #4
0xjnml
On Tue, May 21, 2013 at 6:54 PM, Ian Lance Taylor <iant@golang.org> wrote: > On ...
9 years, 1 month ago (2013-05-22 09:07:50 UTC) #5
iant
On Wed, May 22, 2013 at 2:07 AM, Jan Mercl <0xjnml@gmail.com> wrote: > On Tue, ...
9 years, 1 month ago (2013-05-22 13:31:15 UTC) #6
volker.dobler
PTAL Experimenting with several merging and rotation algorithms convinced me that SymMerge with the simple ...
9 years, 1 month ago (2013-05-30 12:13:36 UTC) #7
volker.dobler
PTAL Experimenting with several merging and rotation algorithms convinced me that SymMerge with the simple ...
9 years, 1 month ago (2013-05-30 12:13:36 UTC) #8
rsc
Thanks very much for working on this. Could you please put the notes from your ...
9 years, 1 month ago (2013-05-30 15:48:26 UTC) #9
volker.dobler
PTAL Stable sorting uses O(n*log(n)*log(n)) calls to Swap, a crude derivation of this is included ...
9 years ago (2013-06-05 10:43:06 UTC) #10
rsc
Looks great, thanks. I admit to not thinking through the algorithm details. If testBentleyMcIlroy says ...
9 years ago (2013-06-10 18:06:29 UTC) #11
volker.dobler
PTAL https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go File src/pkg/sort/sort.go (right): https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go#newcode367 src/pkg/sort/sort.go:367: c := (start + r) / 2 On ...
9 years ago (2013-06-24 21:28:58 UTC) #12
rsc
LGTM Thanks very much. This will be a great addition to Go 1.2.
8 years, 12 months ago (2013-07-02 01:00:54 UTC) #13
rsc
*** Submitted as https://code.google.com/p/go/source/detail?r=7eded0df87b8 *** sort: implement stable sorting This CL provides stable in-place sorting ...
8 years, 12 months ago (2013-07-02 01:20:37 UTC) #14
dfc
On 2013/07/02 01:20:37, rsc wrote: > *** Submitted as https://code.google.com/p/go/source/detail?r=7eded0df87b8 *** > > sort: implement ...
8 years, 12 months ago (2013-07-02 01:34:18 UTC) #15
rsc
Testing a trivial fix now.
8 years, 12 months ago (2013-07-02 01:36:06 UTC) #16
volker.dobler
7 years, 11 months ago (2014-07-20 11:42:36 UTC) #17
Message was sent while issue was closed.
*** Abandoned ***
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b