# 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 : ");
74.         int [] array = new int[size];
75.
76.         for (int i = 0; i < size; i++)
77.         {
78.             System.out.print("\nElement " + (i + 1) + ": ");