Sorting Algorithm: Merge Sort

Sorting Algorithms

• Various sorting algorithms which we will study in this chapter are ‒

1. Insertion sort

2. Merge sort

3. Quick sort

4. Heap sort

 

Sorting Algorithm: Merge Sort

• The merge sort is a sorting algorithm that uses the divide and conquer strategy. In this method division is dynamically carried out.

Algorithm

• Merge sort on an input array with n elements consists of three steps:

■ Divide : Partition array into two sub lists s1 and s2 with n/2 elements each.

■ Conquer : Then sort sub list s1 and sub list s2.

■ Combine : Merge s1 and s2 into a unique sorted group.

 

Example : 1

Sort the following elements using merge sort.

70, 20, 30, 40, 10, 50, 60

Solution :

Now we will split this list into two sublists.

Analysis

• In merge sort algorithm two recursive calls are made. Each recursive call focuses on n/2 elements of the list. After two recursive calls one call is made to combine two sublists i.e. to merge all the elements. We can write it as ‒

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

T(n/2)  → Time taken by left  sublist to get sorted

T(n/2)  →  Time taken by right sublist to get sorted

 Cn      →  Time for combining two sublists

T(n) = O(nlog ₂n)

• The average and worst case time complexity of merge sort is O(nlog ₂n).

C++ program

/***************************************************************

This program is for Merge Sort

*****************************************************************/

#include<iostream>

#include<cstdlib>

using namespace std;

class MS

{

private:

int A[10];

public:

int n;

int low,high;

void get_data();

void MergeSort(int low,int high);

void Combine(int low,int mid,int high);

void Display();

};

/*

This function is to split the list into sublists

*/

void MS::get_data()

{

    cout<<"\n Enter the length of list: ";

    cin>>n;

    cout<<"\n Enter list elements \n";

    for(int i=0;i<n;i++)

        cin>>A[i];

}

void MS::MergeSort(int low,int high)

{

    int mid;

    if(low< high)

    {

        mid = (low+high)/2;//split the list at mid

        MergeSort(low,mid);//first sublist

        MergeSort(mid+1,high);//second sublist

        Combine(low,mid,high);//merging of two sublists

    }

}

/*This function is for merging the two sublists

*/

void MS::Combine(int low,int mid,int high)

{

    int i,j,k;

    int temp[10];

    k=low;

    i=low;

    j=mid+1;

    while(i<= mid && j <= high)

    {

        if(A[i]<<=A[j])

// We compare elements from left sublist and right sublist. If element in the left sublist is lesser than the element in the right sublist then copy that smaller element of left sublist to temp array

        {

            temp[k]=A[i];

            i++;

            k++;

        }

        else

        // We compare elements from left sublist and right sublist. If element in the right sublist is lesser than the element in the left sublist then copy that smaller element of right sublist to temp array

        {

         temp[k]=A[j];

        j++;

        k++;

    }

}

while(i<=mid)

// Reached at the end of right sublist and elements of left sublist are remaining. then copy the remaining elements of left sublist to temp

{

    temp[k]=A[i];

    i++;

    k++;

}

while(j<=high)

// Reached at the end of left sublist and elements of right sublist are remaining. then copy the remaining elements of right sublist to temp

{

    temp[k]=A[j];

    j++;

    k++;

}

//copy the elements from temp array to A

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

A[k]=temp[k];

}

/* function to display sorted array */

void MS::Display()

{

    cout<<"\n\n The Sorted Array Is ...\n";

    for(int i=0;i<n;i++)

        cout<<" "<<A[i];

}

void main()

{

    MS obj:

    clrscr();

    cout<<"\n\t\t Merge Sort \n";

    obj.get_data();

    obj.low=0;

    obj.high‒obj.n‒1;

    obj.MergeSort(obj.low,obj.high);

    obj.Display();

    getch();

}

Output

Merge Sort

Enter the length of list: 7

Enter list elements:

70

20

30

40

10

50

60

The Sorted Array Is …

10 20 30 40 50 60 70

Logic explanation

• To understand above algorithm consider a list of elements as

• Then we will first make two sublists as

• Let us see the combine operation more closely with the help of some example.

• Consider that at some instance we have got two sublits 20, 30, 40, 70 and 10, 50, 60, then

•  Finally we will copy all the elements of array temp to array A. Thus array A contains sorted list.

 

Example : 2

Explain how divide and conquer is applied to merge sort. Trace the algorithm for the following set of data. 25, 0, 8, 78, 6, 34, 56, 90, 100.

Solution :

 

Review Questions

1. Explain how divide and conquer technique can be applied for merge sort.

2. Give short notes of merge sort with suitable example.

3. Write C++ code to implement merge sort with suitable example.