Merge Sort

Merge-sort is based on the divide-and-conquer paradigm. The Merge-sort algorithm can be described in general terms as consisting of the following three steps:


1. Divide Step: If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A₁ and A₂, each containing about half of the elements of A.
2. Recursion Step: Recursively sort array A₁ and A₂.
3. Conquer Step: Combine the elements back in A by merging the sorted arrays A₁ and A₂ into a sorted sequence.

We can visualize Merge-sort by means of binary tree where each node of the tree represents a recursive call and each external nodes represent individual elements of given array A. Such a tree is called Merge-sort tree. The heart of the Merge-sort algorithm is conquer step, which merge two sorted sequences into a single sorted sequence.

To begin, suppose that we have two sorted arrays A₁[1], A₁[2], . . , A₁[M] and A₂[1], A₂[2], . . . , A₂[N]. The following is a direct algorithm of the obvious strategy of successively choosing the smallest remaining elements from A₁to A₂and putting it in A.

MERGE (A₁, A₂, A)

i.← j 1
A₁[m+1], A₂[n+1] ← INT_MAX
For k ←1 to m + n do
    if A₁[i] < A₂[j]
        then A[k] ← A₁[i]
            i ← i +1
        else
            A[k] ← A₂[j]
                j ← j + 1

Merge Sort Algorithm

MERGE_SORT (A)

A₁[1 . . n/2] ← A[1 . . n/2]
A₂[1 . . n/2] ← A[1 + n/2 . . n]
Merge Sort (A₁)
Merge Sort (A₁)
Merge Sort (A₁,A₂, A)

Analysis

Let T(n) be the time taken by this algorithm to sort an array of n elements dividing A into subarrays A₁ and A₂takes linear time. It is easy to see that the Merge (A₁, A₂, A) also takes the linear time. Consequently,

T(n) = T(n/2) + T(n/2) + θ(n)

for simplicity

T(n) = 2T (n/2) + θ(n)

The total running time of Merge sort algorithm is O(n lg n), which is asymptotically optimal like Heap sort, Merge sort has a guaranteed n lg n running time. Merge sort required (n) extra space. Merge is not in-place algorithm. The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program.

Implementation

void mergeSort(int numbers[], int temp[], int array_size)

{
	m_sort(numbers, temp, 0, array_size - 1);

}



void m_sort(int numbers[], int temp[], int left, int right)

{
  int mid;

  if (right > left)

  {

    mid = (right + left) / 2;

    m_sort(numbers, temp, left, mid);

    m_sort(numbers, temp, mid+1, right);


    merge(numbers, temp, left, mid+1, right);

  }

}



void merge(int numbers[], int temp[], int left, int mid, int right)

{

  int i, left_end, num_elements, tmp_pos;


  left_end = mid - 1;

  tmp_pos = left;

  num_elements = right - left + 1;



  while ((left <= left_end) && (mid <= right))

  {

    if (numbers[left] <= numbers[mid])

    {

      temp[tmp_pos] = numbers[left];

      tmp_pos = tmp_pos + 1;

      left = left +1;

    }

    else

    {

      temp[tmp_pos] = numbers[mid];

      tmp_pos = tmp_pos + 1;

      mid = mid + 1;

    }

  }



  while (left <= left_end)

  {

    temp[tmp_pos] = numbers[left];

    left = left + 1;

    tmp_pos = tmp_pos + 1;

  }

  while (mid <= right)

  {

    temp[tmp_pos] = numbers[mid];

    mid = mid + 1;

    tmp_pos = tmp_pos + 1;

  }



  for (i=0; i <= num_elements; i++)

  {

    numbers[right] = temp[right];

    right = right - 1;

  }

}

Merge Sort

Analysis

Implementation

Links