...
On average, quicksort will be faster than mergesort because the partitioning process of breaking the set into "smaller" and a "larger" subsets is less computationally expensive than mergesort's generalized merge operation. On the other hand, if the set is pathological, e.g. it's already sorted, Quicksort will degenerate into a O(N*N) behavior while mergesort will always be O(N*log(N)).
Here are some links to some animations of the Quicksort algorithm (all imperative/procedural code):
- http://www.animatedrecursion.com/intermediate/quicksort.html
- http://www.cs.auckland.ac.nz/software/AlgAnim/qsort.html
- http://pages.stern.nyu.edu/~panos/java/Quicksort/index.html
Here's a very basic implementation of Quicksort in an imperative coding style:
...
The split operations is just the partitioning of the array into two parts, one smaller than the pivot and one larger than the pivot. The split operation corresponds to the "partition" function that many Quicksort implementations identify. The join operation is simply a no-op because the two sorted subsets are disjoint and contiguous, so they are already in order.
...