ANALYSIS DESIGN OF ALGORITHM (ADA) | MERGE SORT

📌Highlight: Hi Friends ! In this post I am going to explain about the concept of merge sort ,Also discuss about their algorithm and function with some example.

Merge sort is based on divide and conquer strategy in which first we try to divide array of N elements to N - sorted array of single elements then merging process merge these sorted array into one sorted array.

Let we understand by the help of an example:

Suppose we have an array of 8 elements such as:

Now we want to sort these elements using merge sort.

First apply divide and conquer strategy and try to divide array of 8 element into two parts in such as way that each part contain sorted elements.

Now here understand the logic:

Here point low as first element and high as last element.

Now we take three variables (F , Mid & S) which work as index pointers point to index and move according to value.

Here first we find the value of Mid so,

    Low = 0

    

    High = 7

    Mid = (Low+ High) / 2

    

    S = Mid + 1

Now we take an temporary array of 8 elements where we place the sorted elements. Take a variable (t) which work as a index pointer in temporary array. Now the temporary array is blank that means it not contain any elements. (t) points first element of array  i.e  t = 0

Now we use while loop here and loop is executing till the condition is true.

Condition is    

        while ( F< = Mid && S < = High )    ----- Condition - 1

Next If the above condition is true than we again check on condition i.e

        If ( a[F] < a[S] )   ---- Condition  - 2

Now if the above condition is true than perform following steps:

    temp[t] = a[F]   // value of a[F] is transferred to temp

    t++  // increment (t) index pointer to 1

    F++  // increment (F) index pointer to 1

if the above condition is false than perform following steps:

    temp[t] = a[S]  // value of a[S] is transferred to temp

    t++

    S++  

Note , If the condition of above while loop become false and still some elements remain then again apply two while loop.

1.  while ( F<= Mid)     ----- Condition - 3

    temp[t] = a[F]      // value of a[F] is transferred to temp

    F++      // increment (F) index pointer to 1

    t++       //increment (t) index pointer to 1

2. while ( S <= High )   ------- Condition - 4

    temp[t] = a[S]    // value of a[S] is transferred to temp

    S++    // increment (S) index pointer to 1

    t++    //increment (t) index pointer to 1

Now by this process finally all the elements get sorted in temporary array.

Now , we need one for loop so that all the sorted element of temporary array are transferred into an array a[i] and get the sorted array.

for ( i=low ; i <= high; i++)

Now Trace by the help of an example:

Tracing:

F	S	Mid	High	Cond-1	Cond-2	Cond-3	Cond-4	temp[t]	a[i]
0	4	3	7	T	F	-	-	2	2
0	5	3	7	T	F	-	-	3	3
0	6	3	7	T	F	-	-	5	5
0	7	3	7	T	T	-	-	9	9
1	7	3	7	T	T	-	-	11	11
2	7	3	7	T	T	-	-	17	17
3	7	3	7	T	F	-	-	19	19
4	8	3	7	F	-	T	F	21	21

LOGIC OF MERGE SORT IN C

Copy Code

#include<stdio.h>

#include<conio.h>

#define max 7

int a[20]={9,6,5,2,3,7,4,8};

int temp[20];

int main()

{

   int i;

   printf("List before sorting\n");

   

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

      printf("%d ", a[i]);

   merge_pass(0, max);

   printf("\nList after sorting\n");

   

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

      printf("%d ", a[i]);

}

void merge_sort(int low,int mid,int high)

{

    int F,S,t,i;

    F = low;

    t = low;

    S = mid+1;

    while(F<=mid && S<=high)

    {

        if (a[F]<a[S])

        {

            temp[t]=a[F];

            F++;          

            t++;

        }

        else

        {

            temp[t]=a[S];  

            S++;

            t++;

        }

    }

    while (F<=mid)

    {

         temp[t]=a[F];

         F++;

         t++;

    }

    while (S<=high)    

    {

        temp [t]=a[S];            

        S++;

        t++;

    }

    for (i=low;i<=high;i++)

    {

        a[i]=temp[i];

    }

       

}

void  merge_pass (int low ,int high)

{

    int mid;

    if(low < high)

    {

      mid=(low + high)/2;

      merge_pass(low, mid);

      merge_pass(mid+1, high);

      merge_sort(low, mid, high);

   }

   else

   {

      return;

   }  

}

OUTPUT:

List before sorting

9 6 5 2 3 7 4 8

List after sorting

2 3 4 5 6 7 8 9

ALGORITHMS OF MERGE SORT

ALGORITHM OF MERGE SORT:

A is an array with N elements.

STEP 1: F = LOW

            F points to first element of first part of array.

STEP 2: S = MID +1

            S point to first element of second part of array.

STEP 3: T = LOW

STEP 4: WHILE ( F <= MID AND S<= HIGH )

STEP 5: If  ( A[F] < A{S] )

STEP 5.1: TEMP [T] = A[F]

STEP 5.2: F = F+1

STEP 5.3: T = T +1

STEP 6: ELSE

STEP 6.1: TEMP [T] = A[S]

STEP 6.2: S= S+1

STEP 6.3: T =T+1

STEP 7: END IF

STEP 8: END WHILE

STEP 9: WHILE ( F <= MID)

STEP 9.1: TEMP [T]

STEP 9.2: F=F+1

STEP 9.3: T=T+1

STEP 10: END WHILE

STEP 11: WHILE ( S<= HIGH)

STEP 11.1: TEMP [T] = A[S]

STEP 11.2: S =S+1

STEP 11.3: T=T+1

STEP 12: END WHILE

STEP 13: FOR ( I=LOW  TO HIGH)

STEP 14: A[I] = TEMP [I]

STEP 15: NEXT I

STEP 16: END

ALGORITHM OF MERGE PASS:

A is an array with N elements , Initially LOW=0 , HIGH=N-1

STEP 1: IF LOW < HIGH

STEP 2: MID = (LOW + HIGH ) /2

STEP 3: RECURSIVELY CALL MERGE_PASS

            Merge_pass(A,LOW,MID)

STEP 4: RECURSIVELY CALL MERGE_PASS

            Merge_pass(A, MID+1, HIGH)

STEP 5: CALL MERGE_SORT

            Merge_sort(A, LOW, MID, HIGH)

STEP 6: END IF

STEP 7: END

EVALUATION OF MERGE SORT

To divide or merge a given array of N-elements into N- sorted array of single element using Divide & Conquer method we must need log₂N passes. Suppose each merging requires at most N- comparisons so the merge sort requires a total of ( N log₂N) comparison with complexity O(Nlog₂N).

📌Friends ! this is all about merge sort, I hope this article is useful for you , I explained the working of merge sort logic with example. so we will in new post till continue reading.