C++ program to sort an array of elements using merge sort

Aim:

To write a program to sort an array of elements using merge sort technique.

Algorithm:

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]

     Else:

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

         [End of if structure. ]

4.    Return.

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.]

6.   Exit.

Program code: