MERGE SORT ALGORITHM
Merge Sort is an algorithm that is more efficient than bubble sorting or insert sorting, but not faster than Quick Sort. The idea is to split the initial array recursively into two approximately equal subarray, left and right. The procedure is then repeated until two elementary arrays of 1 element are reached. Then begins sorting these elementary arrays, and then merging them into larger arrays. In order to form a sorted array when merging, one member of the left and one member of the right subarray is compared in order, and a larger subarray is composed of them, which contains the members of both these small arrays, but in the correct order, ie. . sorted either in ascending or descending order. E.g.
Suppose we have the following sequence that needs to be sorted in ascending order:
Suppose we have the following sequence that needs to be sorted in ascending order:
The task can be solved by recursion.
The process of recursively calling a sorting function begins after entering or initialisation of an array. The function can be called e.g. mergeSort and pass the array itself, the starting position, the end position and the number of elements as a parameter.
The prototype of this function could be:
The process of recursively calling a sorting function begins after entering or initialisation of an array. The function can be called e.g. mergeSort and pass the array itself, the starting position, the end position and the number of elements as a parameter.
The prototype of this function could be:
void mergeSort(int a[ ], int l,int r,int n);
The function should do the following:
- Finds the middle position approximately to determine the left (0, m) and right part of the array (m + 1, n) and initiates further dividing of these two arrays, so that it calls itself again and forwards as a parameter the original array , starting and ending position of both arrays.
- Next performs merging smaller subarrays made in previous recursions.
Deviding an array into smaller subarray
In the next iteration, the initial array will be divided into two arrays when that iteration is completely completed, and this will only be achieved when all subsequently called iterations are completed. The division of the array looks like the following figure:
The function which divide arrays recursively:
void mergeSort(int a[], int l,int r,int n)
{
{
int m=(l+r)/2;
if(l < r)
{
return;
}if(l < r)
{
mergeSort(a, l, m, n); //the left half of a given array
mergeSort(a, m+1, r, n); //the right half of a given array
mergeArrays(a, l, m, r, n); /* Merge left and right arrays. Returning from recursion the sorted subarrays are merged already */
}mergeSort(a, m+1, r, n); //the right half of a given array
mergeArrays(a, l, m, r, n); /* Merge left and right arrays. Returning from recursion the sorted subarrays are merged already */
return;
The recursive deviding process could be illustrated by:
MergeSort function:
When the division of arrays into elementary ones is completed, the elementary arrays are merged into larger arrays and the same are sorted:
Consider the merging process in the 3rd iteration shown in green in the previous figure. Iterations are now counted from the bottom up. Consider two arrays: {3, 5, 10} and {-34, 16}.
After merging you will get: {-34, 3, 5, 10, 16}
Function that does this:
After merging you will get: {-34, 3, 5, 10, 16}
Function that does this:
void mergeArrays(int a[ ], int l, int m, int r, int n)
{
{
int k, i, j;
int aCopy[n];
for(int i=0; i < n; i++)
{
}int aCopy[n];
for(int i=0; i < n; i++)
{
aCopy[i]=a[i];
}The original array a[] is passed as a parameter, as well as the corresponding positions: left l, right r and middle m, as well as the dimension of the array n
void mergeArrays(int a[ ], int l, int m, int r, int n)
{
{
int k, i, j;
int aCopy[ n ];
for(int i=0; i < n; i++)
{
}int aCopy[ n ];
for(int i=0; i < n; i++)
{
aCopy[ i ]=a[ i ];
}
for( i=k=l,j=m+1;i<=m && j<=d;k++){
if(aCopy[ j ] < aCopy[ i ]){
else{
}
a[ k ]=aCopy[ j ];
j++;
}j++;
else{
a[ k ]=aCopy[ i ];
i++;
}i++;
A smaller value overrides the original array a [ ] at its current position "k":
Moves the current position of the part of the copy whose value has been overridden at the original array, as well as the current position of the original array:
Using the loop, we compare the value at the current position of the left array inside the copy with values at the current position of the right-hand side of the array copy:
The next, we copy the remaining elements, if it has any
If some members of the array on the right are smaller than the members of the array on the left, they will be replaced
Let's look main part of application!
Let's look main part of application!
Main part of application
In the main part of the program, you need to specify and allocated a memory for an array, call the method of dividing the array, which further initiates a recursive procedure. when it is finished, the array will be sorted and after that it remains to display it on the screen:
#include < stdio.h >
void printArray(int a[], int n){
int main()
{
void printArray(int a[], int n){
for(int i = 0; i < n; i++)
}
printf("%d ",a[ i ]);
printf("\n");int main()
{
int n;
int a[ ]={ 5, 3, 10, -34, 16, 4, 24, 11, -12, 14};
n = sizeof(a) / sizeof(a[ 0 ]);
mergeSort(a, 0, n-1, n);
printArray(a, n);
return 0;
}int a[ ]={ 5, 3, 10, -34, 16, 4, 24, 11, -12, 14};
n = sizeof(a) / sizeof(a[ 0 ]);
mergeSort(a, 0, n-1, n);
printArray(a, n);
return 0;
This method is significantly faster than bubble sorting because the execution time is linear - logarithmic T (n) = (n * log (n)) as opposed to bubble sorting whose extraction time is square
T(n)=n2