Merge Sort Algorithm

Merge Sort Algorithm Analysis

   

   1)      Divide and Conquer

   2)      Recursive Algorithm

   3)      Stable – It preserve the relative order of records .

   4)      Not In-place i.e. Merge sort is using real memory array and not temporary variables like bubble sort/insertion sort.

    Space complexity O(n)

   5)      Time Complexity O(n*logn)

package com.javadsalgo.Sorting;

public class MergeSort {

      public static void main(String[] args) {

            int unsortedArray[] = { 10, 70, 50, 60, 90, 30 };

            int sortedArray[]=mergeSort(unsortedArray);

            for(int a:sortedArray)

                  System.out.println(a);

      }

      public static int[] mergeSort(int[] unsortedArray) {

            if (unsortedArray.length <= 1)

                  return unsortedArray;

            // Split array in half...

            int length = unsortedArray.length;

            int mid = length / 2;

            int left[] = new int[mid];

            int right[] = new int[length - mid];

            System.arraycopy(unsortedArray, 0, left, 0, mid);

            System.arraycopy(unsortedArray, mid, right, 0, right.length);

            // Sort each half...

            mergeSort(left);

            mergeSort(right);

            // Merge the halves together, overwriting the original array...

            merge(left, right, unsortedArray);

            return unsortedArray;

      }

      public static void merge(int[] left, int[] right, int[] array) {

            int leftLen = left.length, rightLen = right.length, arrayLen =   array.length;

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

            while (i < leftLen && j < rightLen) {

                  if (left[i] <= right[j]) {

                        array[k] = left[i];

                        i++;

                  } else {

                        array[k] = right[j];

                        j++;

                  }

                  k++;

            }

            while (i < leftLen) {

                  array[k] = left[i];

                  i++;

                  k++;

            }

            while (j < rightLen) {

                  array[k] = right[j];

                  j++;

                  k++;

            }

      }

}

Output :

Sorted Array

10,30,50,60,70,90