Merge Sort

Sorting

Sorting refers to the arranging of elements of an array or a list in either ascending or descending order. Let us consider an array a of 4 elements where a=[55,8,4,88].

After sorting it in ascending order they will arrange themselves in [4,8,55,88].

Sorting is a challenging task when the size of the array is large. It requires swapping of data from one memory location to another.

The complexity of sorting increases with size so people are constantly trying to find the most efficient sorting algorithm.

Today we shall discuss one of the efficient sorting algorithm. Merge sort is a general purpose comparison-based sorting algorithm.

Its implementation produces a stable sort. A stable sort algorithm sorts the identical elements in the same order as they appear in the input. If two items are identical then its order is preserved.
Example:
a=[3,5,6,8,5,0] Let us consider this array where the element 5 occurs two times. For our better understanding, let us consider the elements as a=[3,5_a,6,8,5_b,0]. After sorting this array, the order of the element 5 will be preserved in this way. a=[0,3,5_a,5_b,6,8]. Thus this is a stable sort.

Merge Sort

Merge sort uses divide and conquer approach which is a way of diving a complex problem into sub-problems which is relatively easy to solve. The individual results are then combined to get the final solution.

It has two broad steps:
1. Merging
2. Sorting

The diagram below demonstrates merge sort.

Algorithm and Implementation for Merge Sort

Step 1. If the list contain only one element, return the element and terminate operation.
Step 2. Divide the array into two halves until it cannot be further divided.
Step 3. Merge the smaller array in sorted order.

C Functions to Implement Merge Sort

void mergesort(int a[],int left,int right)
{
if(left<right)
{
int mid=(left+(right-1)/2);
mergesort(a,left,mid); //Calling mergesort for 1st Half of the array
mergesort(a,mid+1,right); //Calling mergesort for 2nd Half of the array

merge(a,left,mid,right); //Merge the two sorted sub-arrays
}
}


void merge(int a[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; int L[n1], R[n2]; /* Copy data to temporary arrays L[] and R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } }