On the Worst-Case Complexity of TimSort
drops.dagstuhl.de
drops.dagstuhl.de
"While working on a proper complexity analysis of the algorithm, we realised that there was an error in the last paper reporting such a bug (http://envisage-project.eu/wp-content/uploads/2015/02/sortin...). This implies that the correction implemented in the Java source code (changing Timsort stack size) is wrong and that it is still possible to make it break. This is explained in full details in our analysis: https://arxiv.org/pdf/1805.08612.pdf"
arrayToSort[sum] = 1;
Use:
Integer[] arrayToSort = new Integer[2000000000];
>>> a=[0]*sum(rls)
>>> sum=-1
>>> for i in rls:
... sum += i
... a[sum] = 1
...
>>> a.sort()
>>>
Worst-case complexity.
Also, I needed to bump my JVM heap up to 16GB (not 9GB as recommended), just to run it.
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 49
at java.util.ComparableTimSort.pushRun(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at Test.main(Test.java:80)
arrayToSort[sum] = 1;
There are likely a million ways malformed input can make a java server throw an exception; that's typically how java handles malformed input. It just gets caught and returned as an error to the client.
For sorting algorithms that take the behaviour of modern CPUs into account, check out ips4o (https://arxiv.org/abs/1705.02257, code: https://github.com/SaschaWitt/ips4o) or for a simpler algorithm that's still much faster than quicksort in most cases, blockquicksort (https://arxiv.org/abs/1604.06697, code: https://github.com/weissan/BlockQuicksort). Note that both papers were published in the last two years :)
Of course these algorithms are much more complex and error-prone to implement and use some additional memory, which may explain why they're not used in standard library implementations of popular languages.
So, uh, I guess I just work with the right people :) Sorry that I can't give you anything concrete. All of these papers were presented at ESA (European Symposium on Algorithms), though, so that's a good venue to follow. But beware, ESA has a theory track that's a lot bigger than the experimental track, and papers published there can be somewhat unapproachable ;)
I'd recently asked elsewhere 'I've always wondered is there a good mathematical representation of an algorithm that is useful for algebraic manipulation? Like producing a quicksort from bubble sort.' And got linked this paper [0]. This is only time I've heard the word 'Algoritmics' since that.
Any interesting 'entry level' reads you could send my way?
[0]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45....
I don't think the term 'algorithmics' appears very often in publications, it's more of an umbrella term for many things. The stuff we work in our group is sort of the practical side of theoretical computer science, in that our focus is on algorithms that can be efficiently implemented and don't just look good on paper. The methodology is called Algorithm Engineering, it's described quite well in https://en.wikipedia.org/wiki/Algorithm_engineering. Apart from ESA's track B, the major conferences there are Alenex and SEA (Symposium on Experimental Algorithms). All three are open access.
It's difficult to recommend anything in particular, not only because the scope is very broad, but also because most papers aren't written for a wide audience. Good writing is not something that academics optimize for (perversely, good writing can be seen as a negative point, in that if a paper is easy to understand, it may be rejected for being too simple), nor is it taught. Maybe something like https://github.com/papers-we-love/papers-we-love could serve as a starting point?
It's still a useful and helpful mental exercise but what matters is if I can do an operation cheaper and more reliably than you can. Order of complexity informs that decision but doesn't define it.
Even a moderately sized C is proportional to log(n) for quite a lot of data sets most of us actually work with. Conversely, adding, subtracting or comparing two numbers of arbitrary precision (eg, bignum) takes log(n) time, not O(1) time. Very few algorithms we call < O(n) are implementable in less than O(n log n) as n -> ∞
Complexity analysis is step 2. Step 1 being admitting you have a bottleneck. But there are a lot of other steps after those, with a lot of challenging, specialized work.
We almost always assume that a machine word is large enough to describe the input size n. This usually implies constant-time operations on log(n) bits. Not doing so would clutter up notation and complicate analysis, and the whole point of using models is avoiding that where reasonably possible.
I mean you could take this thinking to the extreme and say that as we live in three-dimensional space, the wire length to access more and more memory has to grow at least with the cube root of the size of the memory, because that memory needs to physically be stored somewhere at the end of the day. That's not helpful for analysing algorithms, though :)
So if you're doing a distributed hash, the base cost of fetching two values to compare them is not only nothing to sneeze at, it is probably fundamental to how you solve the problem.
While more of an implementation detail, you might enjoy:
https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
if you haven't seen it.
Discussed at the time and later, eg:
To the writers defense, they have to algorithm in pseudo code in the article
It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.
Ergo, computer scientists researching the algorithm mathematically must consider the effect of choice of pivot.
The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.
Quickselect requires a pivot choosing strategy; the problem is not only the same as quicksort's, it is the problem from quicksort.
According to Wikipedia, in the worst case, it is O(n²).[1] But that's not strictly correct, IMO. Regardless, it doesn't answer the OP's question of "is there a selection algorithm that operates in worst case O(n)"
[1]: https://en.wikipedia.org/wiki/Quickselect
[2]: https://news.ycombinator.com/item?id=17888755 and the parent comment; specifically, the median-of-medians algorithm is a worst-case O(n) selection algorithm.
See https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".
https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
> A variant of quickselect, the median of medians algorithm, chooses pivots more carefully, ensuring that the pivots are near the middle of the data (between the 30th and 70th percentiles), and thus has guaranteed linear time – O(n). This same pivot strategy can be used to construct a variant of quicksort (median of medians quicksort) with O(n log n) time. However, the overhead of choosing the pivot is significant, so this is generally not used in practice.
> In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively.
> there are actually not one, but two main versions of TimSort. The first version of the algorithm contained a flaw, which was spotted in [5]: while the input was correctly sorted, the algorithm did not behave as announced (because of a broken invariant). This was discovered by De Gouw and his co-authors while trying to prove formally the correctness of TimSort. They proposed a simple way to patch the algorithm, which was quickly adopted in Python, leading to what we consider to be the real TimSort. This is the one we analyze in Sections 3 and 4. On the contrary, Java developers chose to stick with the first version of TimSort, and adjusted some tuning values (which depend on the broken invariant; this is explained in Sections 2 and 5) to prevent the bug exposed by [5]. Motivated by its use in Java, we explain in Section 5 how, at the expense of very complicated technical details, the elegant proofs of the Python version can be twisted to prove the same results for this older version.
[5] Stijn De Gouw, Jurriaan Rot, Frank S de Boer, Richard Bubel, and Reiner Hähnle. Open- JDK’s Java.utils.Collection.sort() is broken: The good, the bad and the worst case. In International Conference on Computer Aided Verification, pages 273–289. Springer, 2015.
Memories on the subject are not great so might be saying bullshit in here
You can call it `m` or `rho` or whatever, just use a different variable.
In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.
In some other typical cases (otherwise sorted array with one element inserted, two sorted arrays appended to each other) rho is 3 and 2, so also O(n).
For instance, timsort is also very fast if only a single element is unsorted, or only two elements, or only three elements. These are not special cases explicitly handled, its just the natural way the algorithm works.
Apparently, the earlier paper had an error, so the implemented fix was not complete.
Still intriguing, though!