Click here to Skip to main content
12,759,971 members (30,424 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as



31 bookmarked
Posted 9 Aug 2014

Merge Sort

, 9 Aug 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
Simple description of Merge Sort


Merge sort is divide and conquer sorting technique where we divide the whole array in to parts then apply merge technique on them and then combine them in order to produce the final sorted array. Merge sort consist  of  two basic algorithms called MERGE and MERGE_SORT.  


The basic algorithm MERGE is the procedure of combining two sorted arrays into a new sorted array.

It is like say there are two arrays,

Now we will apply MERGE technique on it. 

  1. Firstly we will create a new array of size m+n where m is the size of the Arr1 and n is the size of the Arr2. Like in this case m=4 and n=4. Hence our new array Arr3 will of size 4+4=8.                                                  
  2. Now we will have two pointers first pointing at the first position of Arr1 and the other on the 1st position of the Arr2.
  3. Then they go on comparing the values of the two pointers. The pointer with lesser value copy the value to the Arr3 and move a place right.
  4. Now for the first comparison Arr1[0]=1 and Arr2[0]=2. So as 1<2 hence Arr3[0]=1 and the pointer at Arr1[0] incements and now points towards Arr1[1].
  5. Similarly now Arr1[1]=5 and Arr2[0]=2. We know that 2<5 and hence Arr3[1]=Arr2[0]=2. Pointer pointing towards Arr2[0] increments and now pointing towards Arr2[1].
  6. Similarly now Arr1[1]=5 and Arr2[1]=4. We know that 4<5 and hence Arr3[2]=Arr2[1]=4. Pointer pointing towards Arr2[1] increments and now pointing towards Arr2[2].
  7. Similarly after several steps we get,

It actually compares the elements of both the array and choose the small one and add it in the new array.

In this manner the both arrays are combined into a new sorted array.

The algorithm of MERGE is,

MERGE ( A, low1, high1, low2, high2 )

  1. while low1<=high1 and low2<=high2 then
    1. if A[low1] > A[low2] then B[i++] = A[low2++]
    2. else if A[low1] < a[low2] then B[i++] = A[low1++]
    3. else
      1. B[i++] = A[low1++]
      2. B[i++] = A[low2++]
    4. End while
  2. while low1 <= high1
    1. B[i++] = A[low1++]
    2. End while
  3. while low2 <= high2
    1. B[i++] = A[low2++];
    2. End while
  4. for j = low upto j<i 
    1. A[low++] = B[j]
    2. Increment j by 1
  5. End MERGE

Then comes the merge sort algorithm. It actually divide the given array to minimum size and then go on combining the arrays by MERGE to sorted new list.

MERGE_SORT( A, low, high )

  1. if low < high then
    1. mid = ( low+high )/2
    2. MERGE_SORT( A, low, mid )
    3. MERGE_SORT( A, mid+1, high )-
    4. MERGE( A, low, mid, mid+1, high )


The working diagram of the sorting is 

Now consider a MERGE_SORT(A,1,6). Means a Merge sort of an array of 6 elements indexed from 1 to 6.

Th flow of control in this recursive algorithm is,

In case of Time Complexity,

In MERGE() algo we copy n (say) elements of array 1 to array 3 and m (say) elements of array 2 to array 3

So the complexity is O(n+m) which can be said as O(n)

So the complexity of Merging two sorted arrays is O(n)

MERGE_SORT( A, low, high )----------------------------------->T(n)

  1. if low < high then
    1. mid = ( low+high )/2
    2. MERGE_SORT( A, low, mid )----------------------->T(n/2)
    3. MERGE_SORT( A, mid+1, high )------------------->T(n/2)
    4. MERGE( A, low, mid, mid+1, high )---------------->O(n)

So the equation is T(n)=2*T(n/2)+O(n) 

Using Master's theorem, (  Check it by )



It is one of the standard form of merge_sort using C

void merge(int arr1[],int ll1,int ul1,int ll2,int ul2)
    int i=0,k,ll=ll1;
    int arr3[100];
void merge_sort(int arr1[],int ll,int ul)
    int mid;
void main()
    int arr1[100];
    int n,i;
    printf("\nEnter the no. of elements present in the array :");
    printf("\nThe sorted array is...");


This is the standard description of merge sort. It is a divide and conquer method of sorting. Merge sort is a sorting where best,worst and average case time complexities are the same. 


  1. Introduction to Algorithms by CORMEN, LEISERSON, RIVEST, STEIN
  2. ( the moving picture and the url is taken from wikipedia )



This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

India India
I am a student, I write codes and develop desktop based applications in my free time. I have developed many codes in C,Java,C++.I have designed applications in .net,VB using SQL database.

You may also be interested in...

Comments and Discussions

GeneralMy vote of 5 Pin
David A. Gray30-Jun-15 13:56
memberDavid A. Gray30-Jun-15 13:56 
GeneralMy vote of 5 Pin
den2k8830-Oct-14 6:45
memberden2k8830-Oct-14 6:45 
GeneralRe: My vote of 5 Pin
Pritam00728-Feb-15 5:59
memberPritam00728-Feb-15 5:59 
GeneralExcellent! Pin
Christian Amado12-Sep-14 4:30
professionalChristian Amado12-Sep-14 4:30 
GeneralRe: Excellent! Pin
Pritam00728-Feb-15 5:58
memberPritam00728-Feb-15 5:58 
GeneralClear Explanation Pin
sgurukrupa11-Aug-14 23:28
membersgurukrupa11-Aug-14 23:28 
GeneralRe: Clear Explanation Pin
Pritam00728-Feb-15 5:58
memberPritam00728-Feb-15 5:58 
Questionthis sort is also stable! Pin
weldon bailey11-Aug-14 9:16
memberweldon bailey11-Aug-14 9:16 
AnswerRe: this sort is also stable! Pin
Pritam00728-Feb-15 5:57
memberPritam00728-Feb-15 5:57 
GeneralMy vote of 5 Pin
Carlos190711-Aug-14 2:17
memberCarlos190711-Aug-14 2:17 
GeneralRe: My vote of 5 Pin
Pritam00711-Aug-14 3:38
memberPritam00711-Aug-14 3:38 
GeneralVery good Pin
Akhil Mittal 10-Aug-14 19:29
mvp Akhil Mittal 10-Aug-14 19:29 
GeneralRe: Very good Pin
Pritam00711-Aug-14 3:36
memberPritam00711-Aug-14 3:36 
QuestionVery nicely explained Pin
john morrison leon10-Aug-14 8:50
memberjohn morrison leon10-Aug-14 8:50 
AnswerRe: Very nicely explained Pin
Pritam00711-Aug-14 3:37
memberPritam00711-Aug-14 3:37 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170217.1 | Last Updated 10 Aug 2014
Article Copyright 2014 by Pritam007
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid