Merge Sort (Divide and Conquer Method)

Merge Sort:

     

Merge sort is a sorting technique which is based on divide and conquer approach. Given a sequence of n elements a[1]…a[n], the general idea is to split them into two sets a[1]…and…a[n]. Each set is individually sorted and the resulting sorted sequences are merged to produce a single sorted sequence of n elements.

Algorithm MergeSort(low,high)

{

            If(low<high)

            {

                   

                        MergeSort(low,mid)

                        MergeSort(mid+1,high)

                        Merge(low,mid,high)

            }

}

Merge(low,mid,high)

{

            n₁=mid-low+1;

            n₂=high-(mid-1)+1;

            let L(1… n₁+1) and R(1… n₂+1) be two new arrays

            for i=1 to n₁

                 L[i]=A[low+i-1];

            end

            for j=1 to n₂

                 R[j]=A[mid+j];

            end

            L[n₁+1]=;

            R[n₂+1]=;

            i=1

            j=1

            for k=low to high

                        if L[i]≤R[j]

                                    A[k]=L[i]

                                    i=i+1

                        end

                        else A[k]=R[j]

                                    j=j+1

                        end

            end

}

§  Analysis:

If T(n) represents the total computing time required to perform merge sort on an array of n element, then the recurrence relation can be represented as:

Hence, we can say that the complexity of merge sort algorithm is O(nlogn).