So far I have: - Each array k have n elements that are already sorted. - Since t

Question

So far I have:

- Each array k have n elements that are already sorted.

- Since they are already sorted, I can apply the merge of merge sort by merging the first array with the second, the third with the fourth...etc until all arrays have been merged.

- It is O(kn) work to merge the k arrays of size n into k/2 arrays of size 2n, then doing O(kn) work O(logn) times until there is a single array of size kn.

- Thus, run time is O(klogkn).

How would the pseudocode look for this algorithm?

Give an algorithm that gets k sorted arrays (of integers) each of size n as input, and merges them into a single sorted array. Your grade depends on the run time of your algorithm.

Explanation / Answer

Merge sort algorithm is based on the divide-and-conquer paradigm. As we all know its worst-case running time has a lower order of growth in comparison to insertion sort. Since we deal with sub-problems in merge sort, we state each sub-problem as sorting subarray X[q .. r]. Initially, q = 1 and r = n, but these values change as we recurse through sub-problems.

To sort X[q .. r]:

1. Divide Step

If a given array X has 0 or 1 element, simply return; already sorted. Otherwise, split X[q .. r] into 2 subarrays X[q .. s] and X[s + 1 .. r], each containing about half of the elements of X[q .. r]. That is, s is the halfway point of X[q .. r].

2. Conquer Step

Conquer by recursively sorting the two subarrays X[q .. s] and X[s + 1 .. r].

3. Combine Step

Combine the elements back in X[q .. r] by merging the two sorted subarrays X[q .. s] and X[s + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (X, q, s, r).

Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.

Algorithm: Merge Sort

To sort the entire sequence X[1 .. n], make the initial call to the procedure MERGE-SORT (X, 1, n).

MERGE-SORT (X, q, r)

1.     IF q < r                                                    // Check for base case
2.         THEN s = FLOOR[(q + r)/2]                 // Divide step
3.                 MERGE (A, q, s)                          // Conquer step.
4.                 MERGE (A, s + 1, r)                     // Conquer step.
5.                 MERGE (A, q, s, r)                       // Conquer step.

Solution for your question is to create a final output array having size n*k and then 1 by 1 copy all arrays to it.

Finally, use any O(nLogn) sorting algorithm to sort the output array. The time taken by this approach is O(nkLognk) time.

We can also merge all arrays in O(nk*Logk) time using Min Heap.

The detailed algorithm using above scenario:

Step 1: Create an output array of size n*k.

Step 2: Create a min heap of size k, and then insert first element in all the arrays into the heap

Step 3: Repeat the following steps n*k times:

     a) Get minimum element from the heap (always known that minimum is always at root) and store it in the final output array.

     b) Now, replace heap root with the next coming element from the array, from which the element is extracted. If there is no more elements in the array, then replace the root with infinite. Heapify the tree after replacing the root.

Time Complexity:

The most important step is the third step the loop will run n*k times.

In every iteration of the loop, we are calling heapify which will take O(Logk) time. This means that the time complexity is O(nk Logk).

Now the pseudocode will look like this for the above algorithm?

MERGE (A, p, q, r )

      n1 q p + 1
      n2 r q
      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
      FOR i 1 TO n1
            DO L[i] A[p + i 1]
      FOR j 1 TO n2
            DO R[j] A[q + j ]
      L[n1 + 1]
      R[n2 + 1]
    i 1
    j 1
    FOR k p TO r
         DO IF L[i ] R[ j]
                THEN A[k] L[i]
                        i i + 1
                ELSE A[k] R[j]
                        j j + 1

MERGE-SORT(A, p, r)

if p < r

then q b(p + r)/2c

MERGE-SORT(A, p, q)

MERGE-SORT(A, q + 1, r)

MERGE(A, p, q, r)

If you have anykind of problem regarding this question feel free to contact me at pratap_mishra(at)outlook.com.

I also have C, C++ and C# programs with full explanation for this problem if you are in need than email me.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.