4 ms·
Given that the constant factors are so much larger and the number of items relatively small, we're unlikely to start really hitting the theoretical asymptotic c
by JeremyBanks 8y ago
Given that the constant factors are so much larger and the number of items relatively small, we're unlikely to start really hitting the theoretical asymptotic complexities of sorting algorithms in these scenarios. But for what it's worth, like much real-world data, this sounds like a good fit for Timsort: https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort It probably benefits from having a lot more sequential access than random access; the physical world is even more punishing than a processor cache.
- vram22 8y agoTimsort is interesting. I had first read about it some years ago, maybe in the Python Cookbook, 2nd Edition (recommended, BTW, as is Edition 3). It's a hybrid and adaptive sort. From the parent's Wikipedia link: [ Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] and in GNU Octave.[6] ] https://en.wikipedia.org/wiki/Tim_Peters_(software_engineer) https://en.wikipedia.org/wiki/Tim_Peters_(software_engineer) From the above Wikipedia link: [ Peters also wrote the Zen of Python, intended as a statement of Python's design philosophy, which was incorporated into the official Python literature as Python Enhancement Proposal 20 and in the Python interpreter as an easter egg.[8] He contributed the chapter on algorithms to the Python Cookbook[9]. From 2001 to 2014 he was active as a member of the Python Software Foundation's board of directors. Peters was an influential contributor to Python mailing lists.[10] He is also a highly-ranked contributor to Stack Overflow, mostly for answers relating to Python.[11][7] ]