Merge sort

Merge sort

            Let a be an array of n numbers. Our aim is to sort this array in ascending order using merge sort. The steps to be followed are

i)                    Divide the array into n sub arrays with size 1.

ii)                  Merge adjacent pair of sub arrays [a[1]] and [a[2]], [a[3]] and [a[4]], …….,

[a[n-1]] and [a[n]]. Now we will get a n/2 sorted sub arrays of size 2 or less.

iii)                Merge adjacent pairs of sub arrays [a[1]] and [a[2]], [a[3]] and [a[4]], ……., [a[n-3]], [a[n-2]] and [a[n-1

iv)                Repeat this process until ther]], [a[n]]. Now we will get a n/4 sorted sub arrays of size 4 or less.e is only one sub array of size n.

Now this array will be in sorted order

Example

            Sort the given array of numbers in ascending order. Suppose the numbers in the array a are

Procedure

            merge (a, n)    // a – given array,  n – size of the array

            {

                        L = 1 ;  // Initial size of the sub array

            while (L ≤ n) do // size of sub array should be less than n

            {

                        low 1 = 1 ;  //   first element location in the first sub array.

                        k = 1 ;

                        while (low 1 + L ≤ n) do  // to check whether merge is possible

            {

                        low 2 = low 1 + L ;  // to find the second sub array of size L

                        high 1 = low 2 – 1;

                        if ( low 2 + L-1 ≤ n) then

                        high 2 = low 2 + L-1 ;

                        else

                        high 2 = n-1 ;

                        i = low 1 ;

                        j = low 2 ;

                         while ( i≤ high 1 && j ≤ high 2) do

                        {

                           if( a[i] < a[j] then

            {    b[k] = a[j] ; k= k + i ; i= i+1 ; }

                        else

                        {  b[k] = a[j] ; k=k+1 ; j=j+1 ;}

                        }

            while( i≤ high 1) do      // if second sub array becomes empty, copy the remaining                  

            { a[k] = a[i] ;                           //elements from first sub array to array b

                        k = k+1 ;

                        i = i+1 ;

            }

                        while (j≤ high 2) do   //if first sub array becomes empty,

                        {  b[k] = a[j] ;              // copy the remaining elements from

                        k = k+1 ; j = j+1 ;

                        }

                        low 1 = high 2 + 1;   // second sub array to array b

                        }

                        i = low 1;

                                    while ( k ≤ n) do      // to check whether all elements in

                                    {   b[k] = a[i] ;    // array a are compared and copied in b

                                    k = k+1 ; i= i+1 ;

                        }

                        for i = 1 to n do // to copy the elements from b

                        a[i] = b[i] ;   // array to a array to repeat the above process

                        L = 2 * L ;    // to change the size of the sub array.

                        }

                        }