Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?                                                   

Ans.

The list can be developed using Merge sort. Following is the method for it. Assume A is a sorted list with r elements and B is a sorted list with s elements. The operation that combines the elements of A and B into the single sorted list C with n = r +s elements is known as merging.

Procedure 1

MERGING(A, R, B, S, C)

Let A and B be the sorted arrays with R and S elements respectively. The

algorithm merges A and B into an array C with N= R + S elements.

1. [Initialize.] Set NA := 1, NB := 1 and PTR := 1.

2. [Compare.] Repeat while NA <=  R and NB <=  S : If A[NA] < B[NB], then ;

(a)  [Assign element from A to C.] Set C[PTR] := A[NA].

(b)  [Update pointers.] Set PTR := PTR + 1 and

NA := NA + 1. Else:

(a)   [Assign element from B to C.] Set C[PTR]

:= B[NB].

(b)   [Update pointers.] Set PTR := PTR + 1 and

NB := NB + 1.

[End of If structure.] [End of loop.]

3. [Assign remaining elements to C.] If NA > R, then:

Repeat for K = 0, 1, 2,...,S-NB:

Set C[PTR + K] := B[NB + K]. [End of loop.]

Else:

Repeat for K = 0, 1, 2, ..., R - NA:

Set C[PTR + K] := A[NA + K]. [End of loop.]

[End of If structure.]

4. Exit.

Procedure 2:

MERGE(A, R, LBA, S, LBB, C, LBC)

This procedure merges the sorted arrays A

and B into the array C.

1. Set NA := LBA, NB := LBB, PTR := LBC, UBA:= LBA + R - 1, UBB :=     LBB + S - 1.

2. call merging (A,UBA,B,UBB,C)

3. Return.

Procedure 3:

MERGEPASS(A, N, L, B)

The N-element array A consists of sorted subarrays where each subarray has L elements apart from possibly the last subarray, which can have fewer than L elements. The procedure merges the pairs of subarrays of A and assigns them to the array B.

1.   Set Q := INT(N/(2*L)), S:= 2*L*Q and R := N - S.

2.  [Use procedure2 to merge the Q pairs of subarrays.] Repeat for J = 1, 2, . . ., Q:

(a) Set LB := 1 + (2*J - 2) * L. [Finds lower bound of first array.]

(b) Call MERGE(A, L, LB, A, L, LB + L, B, LB). [End of loop.]

3.  [Only one subarray left ?] If R ?  L, then: Repeat for J = 1, 2, . . ., R: Set B(S + J) := A(S+J).

[End of loop.]

Else :

CALL MERGE(A, L, S + 1, A, R, L + S + 1, B, S + 1).

[End of If structure.]

4.   Return.

Procedure 4 MERGESORT( A, N)

This particular algorithm sorts the Nth element array A using an auxiliary array B.

1.   Set L:=1 . [ Initiliazes the number of elements in the subarrays.]

2.   Repeat Steps 3 to 6 while L

3.            Call MERGEPASS(A,N,L,B)

4.            Call MERGEPASS(B,N,2*L,A).

5.             Set L:= 4*L.

[End of Step 2 loop].

6.   Exit.