Interview Preparation Merge Sort

Algorithm for implementation of merge sort is as follows

a. Divide the string into two half using formula (start index + end index)/2, where each half have a new start and end index till one element is left in the leaf node.

b. Starting from leaf node traverse the same route backward:

• Compare the last two nodes.

• Traverse each node whichever element in the node is smaller save the element in the temporary buffer first then save the element of the other node at incremented index in the temporary buffer.

c. Repeat step b until all the elements are copied to the temporary buffer.

d. Store all the elements in the temporary buffer back the main array.

Pseudo Code

void SORT::merge(int *a, int start, int mid, int end)
{
  while(i <= mid && j <= end)
  {
    if(a[i] < a[j])
    {
      temp[k] = a[i];
      i++;
      k++;
    }
    else
    {
      temp[k] = a[j];
      j++;
      k++;
    }
  }
  while(i<= mid)
  {
    temp[k] = a[i];
    i++;
    k++;
  }
  while(j<= end)
  {
    temp[k] = a[j];
    j++;
    k++;
  }
  for(i = start ; i < k ; i++)
  {
    a[i] = temp[i];
  }
}

void SORT::mergesort(int *a, int start, int end)
{
  if (start < end)
  {
    mid = ( (start+end) / 2 );
    SORT::mergesort(a,start, mid);
    SORT::mergesort(a, mid+1, end);
    SORT::merge(a,start, mid, end);
  }
}

For an array with n number of elements,

Best case complexity = Average case complexity = Worst case complexity = O(n log n).

For an animated model refer to following URL http://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-