The algorithm maintains three pointers, one for each of the two arrays and one for maintaining the current index of the final sorted array. The merge step is the solution to the simple problem of merging two sorted lists(arrays) to build one large sorted list(array). The most important part of the merge sort algorithm is, you guessed it, merge step. Merge sort in action The merge Step of Merge SortĮvery recursive algorithm is dependent on a base case and the ability to combine the results from base cases. After that, the merge function picks up the sorted sub-arrays and merges them to gradually sort the entire array. To sort an entire array, we need to call MergeSort(A, 0, length(A)-1).Īs shown in the image below, the merge sort algorithm recursively divides the array into halves until we reach the base case of array with 1 element. p = r.Īfter that, the merge function comes into play and combines the sorted arrays into larger arrays until the whole array is merged. The MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1 i.e. When the conquer step reaches the base step and we get two sorted subarrays A and A for array A, we combine the results by creating a sorted array A from two sorted subarrays A and A. If we haven't yet reached the base case, we again divide both these subarrays and try to sort them. In the conquer step, we try to sort both the subarrays A and A. If q is the half-way point between p and r, then we can split the subarray A into two arrays A and A. A subproblem would be to sort a sub-section of this array starting at index p and ending at index r, denoted as A. When the solution to each subproblem is ready, we 'combine' the results from the subproblems to solve the main problem.

Using the Divide and Conquer technique, we divide a problem into subproblems. Finally, sub-problems are combined to form the final solution. Here, a problem is divided into multiple sub-problems. Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm. Decrease Key and Delete Node Operations on a Fibonacci Heap.

Divide and conquer algorithm