Search

# Merge Sort

It is also a Divide and Conquer algorithm like Quick Sort.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sub lists, each containing one element as a list of one element is considered sorted.

2. Repeatedly merge sub lists to produce new sorted sub lists until there is only one sub list remaining. This will be the sorted list.

Animated Example:

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

Implementation using C:

```#include<stdlib.h>
#include<stdio.h>

// Merges two subarrays of arr[].

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int p = m - l + 1;
int q =  r - m;

/* create temp arrays */
int L[p], R[q];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < p; i++)
L[i] = arr[l + i];
for (j = 0; j < q; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < p && j < q)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < p)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < q)
{
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void merge_Sort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;

// Sort first and second halves
merge_Sort(arr, l, m);
merge_Sort(arr, m+1, r);

merge(arr, l, m, r);
}
}

void print_Array(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr);

printf("Given array is \n");
print_Array(arr, arr_size);

merge_Sort(arr, 0, arr_size - 1);

printf("\n Sorted array is \n");
print_Array(arr, arr_size);
return 0;
} ```

Miscellaneous:

Auxiliary Space: O(n)

Sorting In Place: No in a typical implementation

Stable: Yes

11 views

See All