C++ program to sort an array of elements using merge sort
To write a program to sort an array of elements using merge sort technique.
MERGEPASS(A, N, L, B)
The N- element array A is composed of sorted subarrays where each subarray has L elements except possibly the last subarray, which may 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/(2L)), S : = 2L*Q and R : = N-S.
2. Repeat for J=1, 2, . . . . . ,Q:
(a) Set LB : = 1 + (1J – 2)L. [Finds lower bound of first array.]
(b) Call MERGE (A, L, LB, A, L, LB + L, B, BL).
[End of loop. ]
3. [Only the subarray left ?]
If R<=, then:
Repeat for J=1, 2, . . . . , R:
Set B (S + J) : = A(S=J).
[End of loop]
Call MERGE( A, L, S + 1, A, R, L + S + 1, B, S +1).
[End of if structure. ]
MERESORT (A, N)
This algorithm sorts the N-element array A using an auxiliary array B.
1. Set L : = 1. [Initializes the number of elements in the subarrays.]
2. Repeat Steps 3 to 5 while L < N :
3. Call MERGEPASS (A, N, L, B).
4. Call MERGEPASS (B, N, 2 * L, A).
5. Set L : = 4 * L.
[End of Steps 2 loop.]