Quick sort fun

In last post, we get a feeling about how merge sort works. Merge sort is like a robot. They don't have opinion, they only deduce. When the answer is unknown, they don't make assumption but keep digging down; when something thing is absolutely clear, they make the correct move, then draw correct conclusion. You get stability.  In mathematics  form, The runtime on a problem of size 'n', denoted T(n), can be expressed by the recurrence relation T(n)=2T(n/2) + O(n). Mathematicians have prove that this formula yield best and worst performance as O(nlogn), which is understandable, no matter how "bad" the sorting looks like, merge sort always do the binary dividing and merging, the "badness" didn't alter this process too much.

Quick sort, we will study here, is like merge sort trades some absolute correctness for opportunism, it makes a few (in bad time tons of) wrong moves -- on average, the performance increased a few times than merge sort, however, at bad time, it can stuck at O(n^2) performance -- when n is large, O(n^2) means practically never sort out.

Here is a good story of quick sort.

sort game

A child is given a a pile of mixed balls to sort by size. He asks around where is the best place to start sorting, nobody has any clue. But he has to start somewhere, so, he shoot in the dark, picking the first ball from the pile, then use this ball as a gauge to measure other balls. He now can have opinion with this limited knowledge then starts to move things around. He holds this ball at hand, uses it to compare the rest of the balls. His opinion is so narrowed, he ends up sort the balls into 3 piles. He put the ball he holds at the middle, the smaller balls pile at left, bigger balls pile at right. Oh boy, this simplified view of the problem is too bold.  However, these childish moves didn't do any damage. The pile is a totally random mix, any move with tiny sense in it is moving away from total random, any new state won't be worse than chaotic. At least after these moves, the child gets the first picked ball into the right position. Besides, the total random system now starts to have asymmetry, left and right. Not that bad. After that, the child sorts the the left piles into 3 piles with the same approach; the right side follows. He recursively breaks one bigger piles into 3 smaller piles. Each movements are chaotic, but left a trail of correct middle points behind. At the end of recursions, the middle points connect, and the problem is solved.

Bad story is simple.
Ask this opinionated child to sort an already alined balls and see what will happen.


mergeSort is stable, but it also makes wrong moves. The correctness is relative, it has a scope. During merge sort's merge steps. Each merge moves elements to the right position, at higher level merge, those locally correct positions will be correct with moving again. In the sense of absolute correctness, scientist is also this child. He sometimes makes wrong move at the beginning in top down quicksort, or makes correction at the end in bottom up merge sort.