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.