What is Merge sort? explain with an example

Merge sort

Merge sort follows the divide and rule policy. This algorithm divides the array of N elements into separate smaller arrays and then sorts & rejoins the divided arrays one by one with each other to form the resultant array. Merge sort uses recursion to the achieve division and merge process.

Merge sort algorithm

To explain this sorting technique we take an array elements[] containing N elements.

Two variables "upper" and "lower" stores the upper limit and the lower limit. Starting the process, lower limit starts with the position of first element in the array which is generally zero/0. Upper limit starts with the position of the last element, generally (N-1)th element. The middle position of the array is obtained by adding upper and lower and dividing the result by 2. The obtained position is used to divide the array into two sub arrays. The procedure is followed repeatedly on the sub arrays and the subsequent sub arrays until upper equals lower. This happens when each sub array contains one element each, i.e. when the array has been divided into N sub arrays.

This process can be better explained with an example:

Let an array elements[] contain the following elements:

34 45 89 23 38 76 12 28

The length of the array is 8, so N = 8. Thus lower = 0 (since position of elements in array starts from 0) and upper=s-1=7.

Thus the array will be split from the middle, i.e. (0+7)/2=3 (element at 4th position). The array becomes:

[34 45 89 23] [38 76 12 28]  ([] represents a sub array)

Now each sub array will be considered an individual array and the procedure will be applied to each sub array again.

The left sub array has four elements and so, lower=0 and upper=3. Thus middle point occurs at 1 (position of second element)

The right sub array also has four elements and so, lower=4 and upper=7. Thus the middle point occurs at 5 (position of 6th element)

Thus the sub arrays get divided and the result becomes:

[34 45] [89 23] [38 76] [12 28]

This process is repeated till all sub arrays contain 1 element each.

[34] [45] [89] [23] [38] [76] [12] [28]

The s divided arrays are joined together to form the complete array and the elements are sorted at the same time. This is done by sorting the elements of two arrays while joining them in a third array.

This process can be better explained with an example:

Let us take the divided array shown above:

[34] [45] [89] [23] [38] [76] [12] [28]

The combining procedure takes place as follows:

The single array obtained at the end is the sorted array.

The mergesort algorithm generally contains two distinct methods:

  1. mergesort()
  2. merge()

mergesort() method

mergesort(elements[],lower,upper):This method shares its name with the sorting technique and is generally used to split the array of N elements into N sub arrays each containing 1 element. This is done by using a recursive function for most convenience.

An algorithm for the method is as follows:

Check if upper bound is greater than lower bound else exit Calculate new middle position and divide the array by two halves Call merge sort again for lower half Call merge sort again for upper half Now merge the two halves of the array

/* ======================================= */
/* mergesort method takes three arguments: */
/* elements[] - the array pointer, */
/* lower - the lower limit of the array */
/* upper - the upper limit of the array */
/* ======================================= */
void mergesort (int elements[], int lower, int upper)
{
  int mid; /* stores the position of middle element */
  if (upper > lower)
  {
    /* calculates middle position */
    mid = (lower + upper) / 2; 

    /* recursively splits the left subarray */
    mergesort(elements, lower, mid); 
    
    /* recursively splits the right subarray */
    mergesort(elements, mid + 1, upper); 

    /* merges the separated arrays */
  merge(elements, lower, mid, mid + 1, upper);

  }
}

merge() method

merge(elements[],lower,mid,mid+1,upper):This method joins the two separated arrays into a temporary array before transferring the elements to the original array. The method also sorts the array while joining them.

Let us consider an array elements[] with s elements. Let us also consider that the array has been split into two sub arrays at the middle position.

The array elements[] has been sent to the merge() method along with the position of the first element and the position of the last element of both the sub arrays. Two variables p and q(initialized to the position of the first element of first sub array and second sub array respectively) are used to point to the elements in the arrays.

Now the elements in the two sub arrays are put into a third temporary array D[] in the following manner:

  • The element at p and q are compared.
  • If element at p matches the condition, the element is put into D and p is incremented by 1.
  • If element at q matches the condition, the element is put into D and q is incremented by 1.
  • This is continued till either p or q reaches the last element in its array.
  • If p reaches its end, the remaining elements in the array pointed by q is put in D[] or vice versa.

(The condition refers to elements being greater or lesser than each other.)

After all the elements in the sub arrays have been sorted in D[], the elements are put back into the sub arrays in the order it is present in D[].

Let us take an example to better understand this method:

Let an array elements[] have 8 elements:

23 34 45 89 12 28 38 76

Let it be split up into two sub arrays:

Left sub array: [23 34 45 89]
Right sub array: [12 28 38 76]

p will point to the beginning of left sub array while q will point to the beginning of the second sub array.

The elements will be stored in D[] in the following manner:(considering elements[p] < elements[q] as condition) 

 P			     q				D
[23	34	45	89] [12	   28	  38	76]*	[]

 P			     	   q			D
[23	34	45	89] [12	   28	  38	76]	[12]

 P			     	   q			D
[23	34	45	89] [12	   28	  38	76]*	[12]

 	P			   q			D
[23	34	45	89] [12	   28	  38	76]	[12 23]

        P			   q			D
[23	34	45	89] [12	   28	  38	76]*	[12 23]

 	P			      	  q		D
[23	34	45	89] [12	   28	  38	76]	[12 23 28]

	P			     	  q		D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28]

 		P			  q		D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34]

		P			  q		D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34]

 		P			      	q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38]

		P			     	q	D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34 38]

 			P			q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38 45]

			P			q	D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34 38 45]

 			P			q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38 45 76]

* indicates elements being pointed by p and q are being compared

Since q reaches limit, the remaining element of p is transferred to D[]. Thus the elements of D[] are:

[12 23 28 34 38 45 76 89]

These elements are put into the sub arrays in the order it is present in D[].

An algorithm for this method is as follows:


/* =================================================== */
/* the arguments include: the array pointer elements[], */
/* the position of first element of the left sub array, */
/* the position of last element of the left sub array, */
/* the position of first element of the right sub array, */
/* the position of last element of the right sub array */
/* =================================================== */

void merge (
  int elements[],
  int lower1, 
  int upper1, 
  int lower2, 
  int upper2
)
{
  int p,q,n,j,D[100];

  p = lower1;
  q = lower2;
  n = 0; /* position counter for D[] */

  while ((p <= upper1) && (q <= upper2))
  {
    /* conditionally placing elements in D[] */
    D[n++] = ((elements[p] < elements[q])
               ? elements[p++] : elements[q++]);
  }
  
  while (p <= upper1)
  {
    /* placing remaining elements of */
    /* sub array pointed by p in D[] */
    D[n++] = elements[p++];
  }
  
  while(q <= upper2)
  {
    /* placing remaining elements of */
    /* sub array pointed by p in D[] */
    D[n++] = elements[q++];
  } 

  n = 0;
  
  for (p = lower1; p <= upper1; p++,n++)
  {
    /* placing elements from D[] to left sub array */
    elements[p] = D[n]; 
  }
  
  for (q = lower2,j = n; q <= upper2; q++, j++)
  {
    /* placing elements from D[] to right sub array */
    elements[q] = D[j];
  }
}

Mergesort using array:

#include <stdio.h>

void merge (
  int elements[],
  int lower1, 
  int upper1, 
  int lower2, 
  int upper2
)
{
  int p,q,n,j,D[100];

  p = lower1;
  q = lower2;
  n = 0; /* position counter for D[] */

  while ((p <= upper1) && (q <= upper2))
  {
    /* conditionally placing elements in D[] */
    D[n++] = ((elements[p] < elements[q])
               ? elements[p++] : elements[q++]);
  }
  
  while (p <= upper1)
  {
    /* placing remaining elements of */
    /* sub array pointed by p in D[] */
    D[n++] = elements[p++];
  }
  
  while(q <= upper2)
  {
    /* placing remaining elements of */
    /* sub array pointed by p in D[] */
    D[n++] = elements[q++];
  } 

  n = 0;
  
  for (p = lower1; p <= upper1; p++,n++)
  {
    /* placing elements from D[] to left sub array */
    elements[p] = D[n]; 
  }
  
  for (q = lower2,j = n; q <= upper2; q++, j++)
  {
    /* placing elements from D[] to right sub array */
    elements[q] = D[j];
  }
}

void mergesort (int elements[], int lower, int upper)
{
  int mid; /* stores the position of middle element */
  if (upper > lower)
  {
    /* calculates middle position */
    mid = (lower + upper) / 2; 

    /* recursively splits the left subarray */
    mergesort(elements, lower, mid); 
    
    /* recursively splits the right subarray */
    mergesort(elements, mid + 1, upper); 

    /* merges the separated arrays */
  merge(elements, lower, mid, mid + 1, upper);

  }
}

int main (int argc, char *argv[])
{
  int elements[100], s;
  
  printf (" Enter the size of the array: ");
  scanf ("%d", &s);
  
  printf ("\nEnter the elements of the array:");
  for (i = 0; i < s; i++)
  {
    scanf ("%d", &elements[i]);
  }

  mergesort (elements, 0, s - 1 );

  printf ("\nThe sorted array is:");
  for (i = 0; i < s; i++)
  {
    printf ("\n%d", elements[i]);
  }

}

Mergesort using linked list:

Mergesort may be done using array or linked list. Fully working codes of mergesort using array and linked list has been given below. The programs have been written in C.


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

struct link
{
  int data;
  struct link *next;
};

struct link *getnode()
{
  struct link *n;
  n = (struct link *) malloc (sizeof(struct link));
  return n;
}

int getans()
{
  int i;
  printf ("\n Press 1 to continue and 0 to quit");
  scanf ("%d", &i);
  return i;
}

void putdata(struct link *n)
{
  printf("\n Enter the value:");
  scanf("%d",&(n->data));
  n->next = NULL;
}

void display(struct link *n)
{
  while(n!=NULL)
  {
    printf("\n %d",n->data);
    n = n->next;
  }

}
struct link *merge(struct link *head_one, struct link *head_two)
{
  struct link *head_three;
  if(head_one == NULL)
  {
    return head_two;
  }
  if(head_two == NULL)
  {
    return head_one;
  }
  if((head_one->data) < (head_two->data))
  {
    head_three=head_one;
    head_three->next=merge(head_one->next,head_two);
  }
  else
  {
    head_three=head_two;
    head_three->next=merge(head_one,head_two->next);
  }
  return head_three;
}

struct link *mergesort(struct link *head)
{
  struct link *head_one;
  struct link *head_two;
  
  if ((head==NULL) || (head->next == NULL))
  {
    return head;
  }
  head_one = head;
  head_two = head->next;
  
  while ((head_two != NULL) && (head_two->next != NULL))
  {
    head = head->next;
    head_two = (head->next)->next;
  }
  head_two = head->next;
  head->next = NULL;
  return merge(mergesort(head_one),mergesort(head_two));
}

int main (int argc, char *argv[])
{

  struct link *head,*node;
  head=getnode();
  putdata(head);
  node=head;
  while(getans())
  {
    node->next=getnode();
    node=node->next;
    putdata(node);
  }
  display(head);
  node = mergesort(head);
  printf("\nThe sorted list is:");
  display(node);
  getch();
}

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions