A customer once reported a problem with a product I worked on. The issue involved a user interface intended to show a list of users which were fetched from the

A customer once reported a problem with a product I worked on. The issue involved a user interface intended to show a list of users which were fetched from the database. They said that the software took about an hour to display all the users. The expectation was that it would be pretty much instant. In our testing, we had only tested to 100 users, but when we tried 4000, we couldn't reproduce the problem. It took 5 seconds to show the data, not an hour. It took a long time to track this down. It turned out that the results from the database were in sorted order, and then the UI sorts them for display with quicksort. A list in pre-sorted order is the worst case (n^2) for quicksort. (As an aside, the results were in sorted order, even though the query did not specify that they should be sorted. The reason for this was that this table was loaded into the database from some other source, and that other source outputted the data in sorted order... So, it wasn't just a case of removing a 'ORDER BY' from the query) After thinking about this a bit, I decided to randomize the data after it was fetched, and this brought the time required back down into the sub-10-second range. The problem with sort algorithms is that the worst cases are sometimes fatal to your application, and aren't as rare as you might think. Having an algorithm like timsort that is tuned for these not-so-rare cases sounds quite useful.