Merge Sort Algorithm
- The merge sort algorithm is based on the classical divide-and-conquer paradigm. It operates as follows:
- DIVIDE: Partition the n-element sequence to be sorted into two subsequences of n/2 elements each.
- CONQUER: Sort the two subsequences recursively using the merge sort.
- COMBINE: Merge the two sorted subsequences of size n/2 each to produce the sorted sequence consisting of n elements.
- Note that recursion “bottoms out” when the sequence to be sorted is of unit length.
- Since every sequence of length 1 is in sorted order, no further recursive call is necessary.
- Also, The key operation of the merge sort algorithm is the merging of the two sorted subsequences in the “combine step”.
- Moreover, To perform the merging, we use an auxiliary procedure Merge (A,p,q,r), where A is an array and p,q and r are indices numbering elements of the array such that procedure assumes that the sub-arrays A[p..q] and A[q+1…r] are in sorted order.
- Also, It merges them to form a single sorted subarray that replaces the current subarray A[p..r]. So, Thus finally, we obtain the sorted array A[1..n], which is the solution.
Algorithm for Merge Sort
n1 = q -p + 1
n2 = r – q
let L[1…n1+1] and R[1…n2+1] be new arrays
for i = 1 to n1
L[i] = A[p+i-1]
for j = 1 to n2
R[j] = A[q+j]
L[n1+1] = infinite R[n2+1]= infinite i=1 j=1 for k = p to r
if L[i] ≤ R[j]
i = i +1 else A[k] = R[j]
j = j + 1
MERGE SORT (A,p,r)
if p<r then q<— [ (p + r) / 2 ]
MERGER SORT(A,q + 1,r)
Program for Merge Sort Algorithm
void mergesort(int ,int,int);
int merge(int ,int, int, int);
printf(“Enter size of the array: “);
printf(“Enter %d elements: “,size);
printf(“Sorted elements: “);
void mergesort(int x,int p,int r)
int merge(int x,int p,int q,int r)
n1 = q -p + 1; n2 = r – q;
x[k] = R[j];