Divide and conquer, Quick sort V.S. Merge sort Introduction It’s proved that the best approximate performance of comparison based sorting is O(n lg n ) [1]. In this chapter, two divide and conquer sorting algorithms are introduced. Both of them perform in O(n lg n ) time. One is quick sort. It is the most popular sorting algorithm. Quick sort has been well studied, many programming libraries provide sorting tool based on quick sort. In this chapter, we’ll first introduce the idea of of quick sort, which demonstrates the power of divide and conquer strategy well. Several variants will be explained, and we’ll see when quick sort performs poor in some special cases. That the algorithm is not able to partition the sequence in balance. In order to solve the unbalanced partition problem, we’ll next introduce about merge sort, which ensure the sequence to be well partitioned in all the cases. Some variants of merge sort, including nature merge sort, bottom-up merge sort are shown as well. Similar as other chapters, all the algorithm will be realized in both imperative and functional approaches. |