Analysis of Merge Sort - Algo 5

Merge Sort

The real work of mergesort is done by the merge operation. Given two sorted sub-arrays, together having a total of n elements,  the merge operation uses an auxiliary array of size n to merge them together into a single sorted array in linear time i.e. O(n) in Big Oh notation.

Having this merge operation, mergesort works as follows. Given an array of elements A, it sorts the left and right sub-arrays using mergesort itself, and then merges them together into one single sorted array. The base case is a sub-array of size 1, which is implicitly sorted by definition.

If we analyze the time complexity of mergesort, we will see it is O(n log n) in all cases. That is, the time taken to sort n elements grows proportionally to n log n. Merge sort also needs an extra array of size n for the merge operation. So its space complexity is O(n).

      a)    Merge Sort uses O(n) auxiliary space (extra space).

Space complexity = Auxiliary space + space used by input

     b)    For a merge sort, time complexity is data independent and is always nlogn (      log to the base 2 always), be it worst, best or average case .

     c)     It is a stable sort and there is no worst-case scenario.

Java implementation of Merge Sort

package com.javatutorials.Sort;

import java.util.Scanner;

public class MergeSort2 {

    public static void main(String[] args) {

         Scanner scan = new Scanner(System.in);

         System.out.println("Merge Sort Test\n");

         int n, i;

         /* Accept number of elements */

         System.out.println("Enter number of integer elements");

         n = scan.nextInt();

         /* Create array of n elements */

         int array[] = new int[n];

         /* Accept elements */

         System.out.println("\nEnter " + n + " integer elements");

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

             array[i] = scan.nextInt();

         /* Call method sort */

         mergeSort(array);

         for(i=0;i<array.length;i++)

             System.out.println(array[i]);

    }

    public static void merge(int leftArr[], int rightArr[], int array[]) {

         int nL = leftArr.length;

         int nR = rightArr.length;

         int i = 0, j = 0, k = 0;

         while (i < nL && j < nR) {

             if (leftArr[i] <= rightArr[j]) {

                 array[k] = leftArr[i];

                 i++;

             } else {

                 array[k] = rightArr[j];

                 j++;

             }

             k++;

         }

         // Inserting left over sorted elements directly in array

         while (i < nL) {

             array[k] = leftArr[i];

             i++;

             k++;

         }

         while (j < nR) {

             array[k] = rightArr[j];

             j++;

             k++;

         }

    }

    //10,50,30,40,45

    public static void mergeSort(int[] array) {

         int n = array.length;//5

         if (n <=1 )

             return;

         int mid = n / 2;//2

         int leftArr[] = new int[mid];//2

         int rightArr[] = new int[n - mid];//3

         for (int i = 0; i <= mid - 1; i++)

             leftArr[i] = array[i];

         for (int j = mid; j <= n - 1; j++)

             rightArr[j-mid] = array[j];
      /*System.arraycopy(array, 0, leftArr,0,mid);
      System.arraycopy(array, mid, rightArr,0 ,n-mid);*/          mergeSort(leftArr);

         mergeSort(rightArr);

         merge(leftArr, rightArr, array);

    }

}

Output:

Merge Sort Test

Enter number of integer elements

5

Enter 5 integer elements

40

20

10

50

70

Elements after sorting

10 20 40 50 70