4 ms·

I'd agree, but only as far as aesthetics go. When you have to understand the time complexity and runtime characteristics of the standard library sorting algorit

I'd agree, but only as far as aesthetics go. When you have to understand the time complexity and runtime characteristics of the standard library sorting algorithms, I think Go does a very bad job - the standard `sort.Sort(data sort.Interface)` will run poorly if the data is already mostly sorted. I expect these kinds of things to be documented properly.

jehlakj 8y ago
I was pretty certain most libraries shuffle then quicksort. No need for documentation. Does go not do this?
- eptcyka 8y ago
  Being pretty certain isn't the same as being certain. I really don't care what most libraries do as long as they document what exactly they have chosen to do. Go's `sort.Sort(data Interface)` definitely does not shuffle.
- xapata 8y ago
  Ever heard of Timsort?
  - dgacmu 8y ago
    People were still finding bugs in common implementations of timsort as of 3 years ago. It's not unreasonable to stick with a somewhat more conservative choice for a core library function until there's more reason to have confidence in the implementations of timsort.
    - arayh 8y ago
      This comment got me looking into timsort bugs. This was a really interesting read: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://envisage-project.eu/proving-android-java-and-python-s...
    - IronBacon 8y ago
      You know what, I'm not surprised at all. Didn't one of the most simple algorithms, binary search, suffered of a bug in a standard library (was it Java?) a few years ago? If IIRC it was a corner case, I should check it because I don't recall the details, but it looked robust code. Edit: I think it's this one https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
    - deleted 8y ago
      [deleted]
    - xapata 8y ago
      If I recall correctly, the bug only applied for arrays/lists of length greater than 2 to the more-than-astronomical. Not something that anyone ever encountered in the wild, because current hardware doesn't have enough memory. Edit: The article linked in the other comment says the Java dev team didn't even bother to implement the "proper" fix, but merely adjusted how much space is allocated.
  - NicoJuicy 8y ago
    Timsort always reminds me of monkeysort ( http://leonid-shevtsov.github.io/monkeysort/ http://leonid-shevtsov.github.io/monkeysort/ )
- kazagistar 8y ago
  JVM and Python use timsort, which is O(N) on mostly sorted data of all kinds.
  - sova 8y ago
    timsort is full of win, and such a clever approach.
    - lorenzhs 8y ago
      I'm sorry, but Timsort is a bit of a hack. It's a "this seems to work well" algorithm, and it shows. It took 13 years until its claimed running time was finally proven in 2015. The four (originally three) rules for merging sequences from the stack are rather arbitrary. Multiple issues were found well after it was already widely deployed. Recently, it was also shown that Timsort doesn't optimally use the information it has about runs. As an alternative, powersort was proposed, which seems to outperform Timsort both on randomly ordered inputs as well as inputs with long runs: https://arxiv.org/pdf/1805.04154.pdf https://arxiv.org/pdf/1805.04154.pdf
      - xapata 8y ago
        > a bit of a hack Isn't that most of computing?
      - sova 8y ago
        Totally! And there are much better algorithms for the internet routing protocols, very well documented and tested and all, still just sitting on desks under paperweights...
pjscott 8y ago
It's guaranteed to run in O(n log n) time. Currently it uses quicksort with heapsort as a fallback to prevent quicksort's quadratic worst-case time. https://golang.org/src/sort/sort.go?s=5414:5439#L206 https://golang.org/src/sort/sort.go?s=5414:5439#L206
kragen 8y ago
Golang's `sort.Sort(data sort.Interface)` will sort mostly-sorted data in nearly its fastest possible time, because it basically uses median-of-three quicksort, falling back to insertion sort for small partitions. Median-of-three on sorted or nearly-sorted data picks the optimal or nearly optimal partitioning element for quicksort. The code is simple, readable, and well-commented. Moreover, its average and worst-case complexity is documented in the godoc. In short, your comment is wrong from beginning to end. What led you to believe that anything in it was true?

jehlakj 8y ago

I was pretty certain most libraries shuffle then quicksort. No need for documentation. Does go not do this?

eptcyka 8y ago
Being pretty certain isn't the same as being certain. I really don't care what most libraries do as long as they document what exactly they have chosen to do. Go's `sort.Sort(data Interface)` definitely does not shuffle.
xapata 8y ago
Ever heard of Timsort?
- dgacmu 8y ago
  People were still finding bugs in common implementations of timsort as of 3 years ago. It's not unreasonable to stick with a somewhat more conservative choice for a core library function until there's more reason to have confidence in the implementations of timsort.
  - arayh 8y ago
    This comment got me looking into timsort bugs. This was a really interesting read: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://envisage-project.eu/proving-android-java-and-python-s...
  - IronBacon 8y ago
    You know what, I'm not surprised at all. Didn't one of the most simple algorithms, binary search, suffered of a bug in a standard library (was it Java?) a few years ago? If IIRC it was a corner case, I should check it because I don't recall the details, but it looked robust code. Edit: I think it's this one https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
  - deleted 8y ago
    [deleted]
  - xapata 8y ago
    If I recall correctly, the bug only applied for arrays/lists of length greater than 2 to the more-than-astronomical. Not something that anyone ever encountered in the wild, because current hardware doesn't have enough memory. Edit: The article linked in the other comment says the Java dev team didn't even bother to implement the "proper" fix, but merely adjusted how much space is allocated.
- NicoJuicy 8y ago
  Timsort always reminds me of monkeysort ( http://leonid-shevtsov.github.io/monkeysort/ http://leonid-shevtsov.github.io/monkeysort/ )
kazagistar 8y ago
JVM and Python use timsort, which is O(N) on mostly sorted data of all kinds.
- sova 8y ago
  timsort is full of win, and such a clever approach.
  - lorenzhs 8y ago
    I'm sorry, but Timsort is a bit of a hack. It's a "this seems to work well" algorithm, and it shows. It took 13 years until its claimed running time was finally proven in 2015. The four (originally three) rules for merging sequences from the stack are rather arbitrary. Multiple issues were found well after it was already widely deployed. Recently, it was also shown that Timsort doesn't optimally use the information it has about runs. As an alternative, powersort was proposed, which seems to outperform Timsort both on randomly ordered inputs as well as inputs with long runs: https://arxiv.org/pdf/1805.04154.pdf https://arxiv.org/pdf/1805.04154.pdf
    - xapata 8y ago
      > a bit of a hack Isn't that most of computing?
    - sova 8y ago
      Totally! And there are much better algorithms for the internet routing protocols, very well documented and tested and all, still just sitting on desks under paperweights...

pjscott 8y ago

It's guaranteed to run in O(n log n) time. Currently it uses quicksort with heapsort as a fallback to prevent quicksort's quadratic worst-case time. https://golang.org/src/sort/sort.go?s=5414:5439#L206 https://golang.org/src/sort/sort.go?s=5414:5439#L206

kragen 8y ago

Golang's `sort.Sort(data sort.Interface)` will sort mostly-sorted data in nearly its fastest possible time, because it basically uses median-of-three quicksort, falling back to insertion sort for small partitions. Median-of-three on sorted or nearly-sorted data picks the optimal or nearly optimal partitioning element for quicksort. The code is simple, readable, and well-commented. Moreover, its average and worst-case complexity is documented in the godoc. In short, your comment is wrong from beginning to end. What led you to believe that anything in it was true?