Archive for May, 2009

Dangerous QuickSort

Friday, May 15th, 2009

When it comes to sorting, QuickSort is an all-time-favourite (so I though) and I chose it for implementing a sortable list with data. In some cases (when there were on few changes), it didn’t perform well, to I switched to an old-fashioned bubble-sort in such cases.

What I had to learn now, is that if the data that has to be sorted, is arranged in the right / unfortunate way, then QuickSort can easily crash your program by consuming excessively stack space and finally causing a stack overflow. You won’t need much data for this. 10,000 items is enough to perform terribly slow and finally crashing the software.

I switched to IntroSort, which seams to work better (so far) and (according to Wikipedia) behaves better in worst-scenarios than QuickSort. We’ll see. Sample implementations for IntroSort are rare, but I found one linked in this blog.