MergeSort In Java
- Uses Divide and Conquer strategy like QuickSort.
- It divides the array of numbers into sub-arrays (from middle) until there is only one element in each sub-array.
- These sub-arrays are then merged into sorted sub-arrays until we obtain a sorted merged array.
- Stable
- Best Case Time Complexity: O(n log n)
- Worst Case Time Complexity: O(n log n)
- Space Complexity: O(n)
public class MergeSortInJava { void sort(int arr[], int l, int r) { if (l < r) { // Find mid int m = (l+r)/2; // Sort first and second halves with recursion sort(arr, l, m); sort(arr , m+1, r); // Merging the sorted halves... merge(arr, l, m, r); } } // Merges two subarrays (halves) of arr[]. // First subarray is arr[l] <--> arr[m] // Second subarray is arr[m+1] <--> arr[r] void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays so that // we can create temporary arrays of same size // and for while condition int n1 = m - l + 1; // + 1 as size should be 1 for single element where m = l = 0 int n2 = r - m; /* Create temp arrays */ int leftTempArr[] = new int [n1]; int rightTempArr[] = new int [n2]; /*Copy data to temp arrays*/ for (int i=0; i<n1; i++) leftTempArr[i] = arr[l + i]; // lowest index + i for (int j=0; j<n2; j++) rightTempArr[j] = arr[m + 1+ j]; // (mid+1) + j /* Merge the temp arrays */ // Initial indexes of first and second subarrays int i = 0, j = 0; // Initial index of merged subarry array // Put number whichever is lower in arr[k] int k = l; while (i < n1 && j < n2) { if (leftTempArr[i] <= rightTempArr[j]) { arr[k] = leftTempArr[i]; i++; } else { arr[k] = rightTempArr[j]; j++; } k++; } /* Copy remaining elements of leftTempArr[] if any */ while (i < n1) { arr[k] = leftTempArr[i]; i++; k++; } /* Copy remaining elements of rightTempArr[] if any */ while (j < n2) { arr[k] = rightTempArr[j]; j++; k++; } } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; i++) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = {11, 10, 12, 4, 5, 6}; System.out.println("Unsorted:"); printArray(arr); MergeSortInJava ob = new MergeSortInJava(); ob.sort(arr, 0, arr.length-1); System.out.println("\nSorted:"); printArray(arr); } } /* OUTPUT: Unsorted: 11 10 12 4 5 6 Sorted: 4 5 6 10 11 12 */ MergeSort Analysis
public class MergeSortAnalysis { void sort(int arr[], int l, int r) { if (l < r) { // Find mid int m = (l+r)/2; System.out.println("`````````````````````"); System.out.println("l: " + l + " | m: " + m + " | r: " + r); System.out.println("`````````````````````"); // Sort first and second halves with recursion sort(arr, l, m); sort(arr , m+1, r); // Merging the sorted halves... merge(arr, l, m, r); } } // Merges two subarrays (halves) of arr[]. // First subarray is arr[l] <--> arr[m] // Second subarray is arr[m+1] <--> arr[r] void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays so that // we can create temporary arrays of same size // and for while condition int n1 = m - l + 1; // + 1 as size should be 1 for single element where m = l = 0 int n2 = r - m; /* Create temp arrays */ int leftTempArr[] = new int [n1]; int rightTempArr[] = new int [n2]; /*Copy data to temp arrays*/ for (int i=0; i<n1; i++) leftTempArr[i] = arr[l + i]; // lowest index + i for (int j=0; j<n2; j++) rightTempArr[j] = arr[m + 1+ j]; // (mid+1) + j System.out.println("--------------------"); System.out.println("LEFT HALF"); printArray(leftTempArr); System.out.println("--------------------"); System.out.println("--------------------"); System.out.println("RIGHT HALF"); printArray(rightTempArr); System.out.println("--------------------"); /* Merge the temp arrays */ // Initial indexes of first and second subarrays int i = 0, j = 0; // Initial index of merged subarry array // Put number whichever is lower in arr[k] int k = l; while (i < n1 && j < n2) { if (leftTempArr[i] <= rightTempArr[j]) { arr[k] = leftTempArr[i]; i++; } else { arr[k] = rightTempArr[j]; j++; } k++; } /* Copy remaining elements of leftTempArr[] if any */ while (i < n1) { arr[k] = leftTempArr[i]; i++; k++; } /* Copy remaining elements of rightTempArr[] if any */ while (j < n2) { arr[k] = rightTempArr[j]; j++; k++; } } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; i++) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = {11, 10, 12, 4, 5, 6}; System.out.println("****************"); System.out.println("Unsorted:"); printArray(arr); System.out.println("****************"); MergeSortAnalysis ob = new MergeSortAnalysis(); ob.sort(arr, 0, arr.length-1); System.out.println("****************"); System.out.println("Sorted:"); printArray(arr); System.out.println("****************"); } } /* OUTPUT: **************** Unsorted: 11 10 12 4 5 6 **************** ````````````````````` l: 0 | m: 2 | r: 5 ````````````````````` ````````````````````` l: 0 | m: 1 | r: 2 ````````````````````` ````````````````````` l: 0 | m: 0 | r: 1 ````````````````````` -------------------- LEFT HALF 11 -------------------- -------------------- RIGHT HALF 10 -------------------- -------------------- LEFT HALF 10 11 -------------------- -------------------- RIGHT HALF 12 -------------------- ````````````````````` l: 3 | m: 4 | r: 5 ````````````````````` ````````````````````` l: 3 | m: 3 | r: 4 ````````````````````` -------------------- LEFT HALF 4 -------------------- -------------------- RIGHT HALF 5 -------------------- -------------------- LEFT HALF 4 5 -------------------- -------------------- RIGHT HALF 6 -------------------- -------------------- LEFT HALF 10 11 12 -------------------- -------------------- RIGHT HALF 4 5 6 -------------------- **************** Sorted: 4 5 6 10 11 12 **************** */