> I can't tell you how often I'm sorting something with someone (like Christmas ornaments) and want to explain the fastest route to sorting them.
I'm imagining you using quicksort to sort ornaments, but then I started thinking that sorting algorithms aren't as helpful in real life as they are with computers because your brain can comprehend "the big picture" and do precision swaps or innovative transformations that a computer wouldn't know to do.
For example, say you need to slide some wooden blocks into a long slender box. The blocks have letters of the alphabet on them, and you want to load them such that z is in the very bottom and a it at the very top. You arrive at the table and you see the blocks are sorted - but in the reverse order. You could use a sorting algorithm to optimally correct this, or you could just flip the box over and load from the other side...
My favorite solution like this I saw was from grading an Algorithms class.
The assignment was "turn this min-heap implementation into a max-heap implementation". The correct solution was to flip the tests correctly.
The solution I liked the best just negated all the values as they came in, and negated them again as they came out, so as long as you were inserting numeric values, everything worked out! It was a) delightful and b) totally missing the point of the assignment, so I felt bad about marking it down, but the point was to demonstrate knowledge of heaps, and the proposed solution would have worked whether the internals were a heap or not.
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 It probably benefits from having a lot more sequential access than random access; the physical world is even more punishing than a processor cache.
Timsort 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] ]
[ 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] ]
I'm imagining you using quicksort to sort ornaments, but then I started thinking that sorting algorithms aren't as helpful in real life as they are with computers because your brain can comprehend "the big picture" and do precision swaps or innovative transformations that a computer wouldn't know to do.
For example, say you need to slide some wooden blocks into a long slender box. The blocks have letters of the alphabet on them, and you want to load them such that z is in the very bottom and a it at the very top. You arrive at the table and you see the blocks are sorted - but in the reverse order. You could use a sorting algorithm to optimally correct this, or you could just flip the box over and load from the other side...