Last Updated On: June 19, 2016
Editor: Adeeb C

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

Category: C++,Programing
Tags

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: