There are ways to make the n^2 worst case extraordinarily unlikely, and there is a way to make it impossible (though it is highly technical). Some others have

There are ways to make the n^2 worst case extraordinarily unlikely, and there is a way to make it impossible (though it is highly technical). Some others have posted methods (random pivot, median of 3). The gnu libc qsort implementation is a good learning tool (it uses median of 3). I think CLRS has the guaranteed n log n version.