Divide and Conquer

We had started discussing three new sorting algorithms; merge sort, quick sort and heap sort. All of these three algorithms take time proportional to nlog₂n. Our elementary three sorting algorithms were taking n² time; therefore, these new algorithms with nlog₂n time are faster. In search operation, we were trying to reduce the time from n to log₂n.

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)

We know that elementary three sorting algorithms were taking approximately n² time. Suppose we are using insertion sort of those elementary algorithms. We divide the list into two halves then the time will be approximately (n/2)2+(n/2)2. The time required for merging operation is approximately n. This operation contains a simple loop that goes to n.

Suppose that n is 100. Considering if we apply insertion sort algorithm on it then the time taken will be approximately (100)² = 10000. Now, if we apply divide and conquer technique on it. Then for first half approximate time will be (100/2)². Similarly for second half it will be (100/2)². The merging approximate time will be 100. So the whole operation of sorting using this divide and conquer technique in insertion sort will take around (100/2)² + (100/2)²+100 = 5100. Clearly the time spent (5100) after applying divide and conquer mechanism is significantly lesser than the previous time (10000). It is reduced approximately to half of the previous time. This example shows the usefulness of divide and conquer technique.

By looking at the benefit after dividing the list into two halves, some further questions arise:

- Why not divide the halves in half?

- The quarters in half?

- And so on . . .

- When should we stop?

At n = 1

So we stop subdividing the list when we reach to the single element level. This divide and conquer strategy is not a thing, we have already prepared binary search tree on the same lines. One side of the tree contains the greater elements than the root and other part contains the smaller elements. Especially, when performing binary search in an array, we had started our search from mid of it. Subdivided the array and kept on comparing and dividing the array until we got success or failure. The subdivision process may prolong to individual element of the array.

Hence, we used to perform binary search on the same lines of divide and conquer strategy. Remember, we applied binary search on sorted array. From this one can realize that sorting facilitates in searching operations.

In figure 45.3, in order to sort the list, we have divided the list in the two parts and each part is subdivided into further subparts. At end each part is consisting of either single element or maximum two elements. If we have two numbers to sort, we can compare them (or sort them) with single if statement. After sorting individual subparts, we start merging them in the upward direction as shown in the figure Fig 45.4.

In Fig 45.4, we have four sorted smaller parts. We combine them to become two sorted parts and two sorted parts are further combined or merged to become one sorted list.

Technorati Tags: divide and conquer,divide and conquer algorithm,data structure,divide and conquer rule,divide and conquer algo