fueanta

Merge Sort in Java.

Jun 2nd, 2017
129
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Author : Taqui
  3.  * Algorithm Name : Merge Sort
  4.  * Time Complexity : O(n.log(n))
  5.  */
  6.  
  7. import java.util.Scanner;
  8.  
  9. public class MergeSort {
  10.     public int[] originalList; // saves the main list of data
  11.     public int[] sortedList; // saves the sorted data
  12.     int size; // total number of data
  13.  
  14.     public MergeSort(int[] originalList) {
  15.         this.originalList = originalList.clone();
  16.         this.sortedList = originalList;
  17.         this.size = originalList.length;
  18.  
  19.         divide(0, size - 1); // starting merge sort
  20.     }
  21.  
  22.     public void divide(int low, int high) {
  23.         if (low != high)
  24.         {
  25.             int middle = (low + high) / 2;
  26.             divide(low, middle); // first half
  27.             divide(middle + 1, high); // second half
  28.             merge(low, high); // sort and join both
  29.         }
  30.     }
  31.  
  32.     public void merge(int low, int high) {
  33.         int demoList[] = new int[(high - low) + 1]; // demo list to hold the merged data after sorting
  34.         int middle = (low + high) / 2;
  35.         int i1 = low, i2 = middle + 1, I = 0;
  36.  
  37.         // i1 and i2 will iterate through the first list and second list respectively
  38.         // I will iterate through the demo list to merge sorted data
  39.  
  40.         while (i1 <= middle && i2 <= high) // i1-> 0 to middle, i2-> middle + 1 to last
  41.         {
  42.             if (sortedList[i1] <= sortedList[i2])
  43.             {
  44.                 demoList[I++] = sortedList[i1++];
  45.             }
  46.             else
  47.             {
  48.                 demoList[I++] = sortedList[i2++];
  49.             }
  50.         }
  51.  
  52.         // left over of first list
  53.         while (i1 <= middle)
  54.         {
  55.             demoList[I++] = sortedList[i1++];
  56.         }
  57.         // left over of second list
  58.         while (i2 <= high)
  59.         {
  60.             demoList[I++] = sortedList[i2++];
  61.         }
  62.  
  63.         // copying back the merged data into main list..to merge this with another sorted list
  64.         for (int i = low; i <= high; i++)
  65.         {
  66.             sortedList[i] = demoList[i - low];
  67.         }
  68.     }
  69.  
  70.     public static void main(String[] args) {
  71.         Scanner read = new Scanner(System.in);
  72.         System.out.print("Size of the List : ");
  73.         int size = read.nextInt();
  74.         int [] array = new int[size];
  75.  
  76.         for (int i = 0; i < size; i++)
  77.         {
  78.             System.out.print("\nElement " + (i + 1) + ": ");
  79.             array[i] = read.nextInt();
  80.         }
  81.  
  82.         System.out.print("\nSorted list: ");
  83.         MergeSort ms = new MergeSort(array);
  84.         for (int i : ms.sortedList)
  85.         {
  86.             System.out.print(i + " ");
  87.         }
  88.     }
  89. }
RAW Paste Data