We had started discussing three new sorting algorithms; merge sort, quick sort and heap sort. All of these three algorithms take time proportional to nlog2n. Our elementary three sorting algorithms were taking n2 time; therefore, these new algorithms with nlog2n time are faster. In search operation, we were trying to reduce the time from n to log2n.
Let’s discuss these sorting algorithms; merge sort, quick sort and heap sort in detail.
We had started our discussion from divide and conquer rule where we also saw an example. Instead of sorting a whole array, we will divide it in two parts, each part is sorted separately and then they are merged into a single array.
Let’ see few analysis to confirm the usefulness of the divide and conquer technique.
- To sort the halves approximate time is (n/2)2+(n/2)2
- To merge the two halves approximate time is n
- So, for n=100, divide and conquer takes approximately:
= (100/2)2 + (100/2)2 + 100
= 2500 + 2500 + 100
= 5100 (n2 = 10,000)