Merge Sort Algorithm


The algorithm of merge sort also falls in the category of divide and conquer that is the array or the list is split into halves first and then it is sorted in ascending or descending order.

When the two divided array or lists are sorted then they are merged together to form one array. We can also implement merge sort recursively that is the function or method of the merge will call itself.

There are three main steps that are involved in merge sorting:

  1. If the number of the items to be sorted is 0 or 1 then return
  2. The first and second halves of the array should be sorted recursively
  3. Then merge the two sorted parts of the array together into a single sorted group.

In merge sorting algorithm, the array or list is not divided into two parts only rather the list is divided into n sub lists. Each of the sub lists has one element; this is because the list that has one element is considered to be a sorted list.

These sub lists are then merged together and one sorted list is produced. The complexity time of merge sorting is O (n log n). The algorithm of merge sort is fast. Merge sort is also considered stable as two same elements in a list won’t change rather they will be sorted in same order in the sorted list.


How merge sort works:

Suppose we have a list of elements and we want to sort it in ascending order by using merge sort. The list of elements will be first divided into sub lists.

These sub lists will have only one element and they will be considered sorted and then they will be merged together and we will get a final sorted list of elements. In other words we can say that merge sort is used to break the unsorted list of elements into sorted sub lists and then these sub lists are merged together to form a single sorted list of elements.

Consider the following diagram and you will get the main idea of algorithm of merge sorting:

main idea of algorithm

I can be seen in the above figure that first we had a list of number of elements, then this list is divided into further two lists and that two sub lists are further divided. This process continues until the sub list has only one element.


Sorting using Merge Sort Algorithm:

The following is the algorithm of merge sort:

ALGORITHM:

int arr [5] = {34, 65, 23, 15};

void mergesorting (int arr [], int s, int e)

{

int n;

if (s < e)

{

n = floor ((s + e) / 2);

mergesorting (arr, s, n);

mergesorting (arr, n + 1, e);

mergesorting (arr, s, n, e);

}

}

void merging (int arr [], int s, int n, int e)

{

int array [5];

int x, y, l;

l = 0;

x = s;

y = n + 1;

while(x < = n && y < = e)

  {

    if (arr [x] < arr [y])

    {

      array [l ++] = arr [x ++];

    }

    else

    {

      array [l ++] = arr [y ++];

    }

  }

  while (x < = n)

  {

    array [l ++] = arr [x ++];

  }

  while (y < = e)

  {

    array [l ++] = arr [y ++];

  }

  for (x = e; x > = s; x –)

  {

    arr [x] = array [– l];

  }

}

The working of the above algorithm involves splitting the array into sub arrays until the array has one element left which is considered as sorted one. Then these sub arrays are merged together to form a single sorted one. In the above algorithm, the variable “s” is used for the first index of the array that is its value is 0 and the variable “e” represents the last index of the array.

Then an array of size 5 is declared. Merge sorting is done recursively that is the method in which merge sorting is implemented calls itself. In the algorithm we have another method named void merging (int arr [], int s, int n, int e), that is used to merge the sorted sub arrays.


Complexity Analysis of Merge Sort:

The following are the cases for time complexity of merge sorting:

Worst case Time complexity:

The worst case time complexity is o (n log n)

Best case Time Complexity:

The best case time complexity is o (n log n)

Average Time Complexity:

The average case time complexity is o (n log n)

Space Complexity:

The space complexity is o (n)

In merge sorting when the array or list is divided into halves, it takes a linear time to merge them together and hence the time complexity of merge sort in all the cases that are best, average and worst is the same that is O (n log n). Merge sorting also takes an equal amount of space (additional space) as taken by an unsorted list. Therefore, we do not use merge sorting algorithm to search large unsorted lists. To sort a linked list we use merge sorting algorithm.