Question

Design and analysis of Algorithms: How do I write a k way merge sort algorithm from a merge sort algorithm that splits 2 arrays while sorting?

Answer 1

Merge Sort and K way Merge Sort

Hey Student, get ready lets us grease up our mind for the Data Structure lesson on Merge sort and K way merge sort. We will be learning merge sort and k way merge sort and how we can analysis and design to solve write a k way merge sort algorithm from a merge sort algorithm that splits 2 arrays while sorting

Merge Sort

Here, arr[] is the input array, l is left index and r is right index

MergeSort(arr[], l, r)

If r > l

     1. Find the middle point to divide the array into two halves:

             middle m = (l+r)/2

    2. Call mergeSort for first half:  

             Call mergeSort(arr, l, m)

     3. Call mergeSort for second half:

             Call mergeSort(arr, m+1, r)

     4. Merge the two halves sorted in step 2 and 3:

             Call merge(arr, l, m, r)

Time complexity of Merge Sort is O(nLogn)  in all 3 cases (worst, average and best)

We can use the above algorithm to sort the array in K way Merge Sort. In K way merge sort k is the no of arrays that we want to merge that are sorted, we can use merge sort to sort the arrays if not already sorted.

K way Merge Sort

An efficient solution is to use heap data structure. The time complexity of heap based solution is O(N Log k).

1. Create an output array.
2. Create a min heap of size k and insert 1st element in all the arrays into the heap
3. Repeat following steps while priority queue is not empty.
     a) Remove minimum element from heap (minimum is always at root) and store it in output array.
     b) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.

Example: k=3

arr[][] = { {1, 3},

                  {4, 2 , 6},

                  {10, 0, 9, 11}} ;

In the above k arrays are not sorted, use merge sort algorithm to sort them, below are the sorted array after merge sort.

arr[][] = { {1, 3},

                  {2, 4, 6},

                  {0, 9, 10, 11}} ;

Now we will put k way merge sort using min heap, taking all the first element of the array and put them in the heap and checking for the min value and put them in the output array. Below is the output after k way merge sort.

Min heap: 1 , 2 , 0

Output array: [0]

Min heap: 1 , 2, 9

Output array: [0, 1]

Min heap : 3 , 2 , 9

Output array: [0, 1, 2]

Min heap : 3 , 2 , 9

Output array: [0, 1, 2]

.

.

.

Similarly on each step, we take the min value from the heap and put in the output array to get the final k way sorted array.

Output: 0 1 2 3 4 6 9 10 11