On the Worst-Case Complexity of TimSort

Re:On the Worst-Case Complexity of TimSort by wiz21c on Friday August 31, 2018 @04:32AM (#17883897)

I'd say it the other way around : 1/ it's amazing that a code that is used in countless occurences can still have a bug; 2/ (I've studied sorting algorithms for a while) finding such a bug is very clever... Kudo's to the authors.

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by willtim on Friday August 31, 2018 @06:09AM (#17884304)

What's amazing is how little understanding we seem to have over such critical widely-used code. Java opted for a complex and arguably unproven algorithm, so it was always a risk. We now have functional languages that are able to express provably correct sorting algorithms, so the bar is getting higher.

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by elygre on Friday August 31, 2018 @05:03AM (#17884042)

The java bug (https://bugs.openjdk.java.net/browse/JDK-8203864) has some more information on the history, including a reference to an earlier paper from 2015 relating to the same problem.

Apparently, the earlier paper had an error, so the implemented fix was not complete.

Still intriguing, though!

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by pvg on Friday August 31, 2018 @05:58AM (#17884261)

It looks deceptively like it but 'kudos' is not plural of a kudo (or reference to some awesome thing Kudo once did).

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by klmr on Friday August 31, 2018 @06:51AM (#17884469)

… and even if it were a plural the apostrophe would be misplaced.

[ Parent | on HN ]

Re:On the Worst-Case Complexity of TimSort by basil-rash on Friday August 31, 2018 @10:30AM (#17885869)

Is it really not? The dictionary says otherwise, albeit by back-formation (as is the English way).

https://www.merriam-webster.com/dictionary/kudo

[ Parent | on HN ]