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

Bubble Sort, Selection Sort and Insertion Sort

Sorting Algorithms with complexity o(n^2)

Bubble Sort

public class BubbleSort {

      public static void main(String[] args) {

            int num[] = new int[] { 20, 13, 23, 19, 29, 1 };

            for (int i = 0; i <= (num.length) - 2; i++) {

                  for (int j = 0; j <= (num.length) - 2 - i; j++) {

                        if (num[j] > num[j + 1]) {

                              int temp = num[j];

                              num[j] = num[j + 1];

                              num[j + 1] = temp;

                        }

                  }

            }

            StringBuffer sb = new StringBuffer();

            for (int i : num) {

                  sb.append(i).append(" ");

            }

            System.out.println(sb.toString());

      }

}

Selection Sort

package com.javaetutorials;

/*Finding the smallest element and swapping with the first element ,

 thus fixing the starting position to the last position*/

public class SelectionSort {

      public static void main(String[] args) {

            int num[] = new int[] { 20, 13, 23, 19, 29, 1 };

            for (int i = 0; i <= num.length - 2; i++) {

                  // Min index is the first element of unsorted list

                  int min = i;

                  /*

                   * Find minimum element index in Unsorted List. Update the Minimum

                   * element index.

                   */

                  for (int j = i + 1; j <= num.length - 1; j++) {

                        if (num[j] < num[min])

                              min = j;

                  }

                  int temp = num[min];

                  num[min] = num[i];

                  num[i] = temp;

            }

            for (int arr : num)

                  System.out.print(arr + ",");

      }

}

Insertion Sort

package com.javaetutorials;

public class InsertionSort {

          public static void main(String[] args) {

                   int num[] = new int[] { 20, 13, 23, 19, 29, 1 }, i, j, key;

                   for (i = 1; i <= num.length - 1; i++) {

                             key = num[i];

                             j = i - 1;

                             while (j >= 0 && key < num[j]) {

                                      num[j + 1] = num[j];

                                      j--;

                             }

                             num[j + 1] = key;

                   }

                   for (int arr : num)

                             System.out.print(arr + ",");

          }

}

< in highlighted portion making it Stable Sort whereas <= will move the element to left and thus making it Unstable Sort.