Merge Sort Program

Program: Implement merge sort in java. Merge sort is a divide and conquer algorithm. Steps to implement Merge Sort: 1) Divide the unsorted array into n partitions, each partition contains 1 element. Here the one element is considered as sorted. 2) Repeatedly merge partitioned units to produce new sublists until there is only 1 sublist remaining. This will be the sorted list at the end. Merge sort is a fast, stable sorting routine with guaranteed O(n*log(n)) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array. Merge sort is relatively simple to code and offers performance typically only slightly below that of quicksort. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 public class MyMergeSort {           private int[] array;     private int[] tempMergArr;     private int length;       public static void main(String a[]){                   int[] inputArr = {45,23,11,89,77,98,4,28,65,43};         MyMergeSort mms = new MyMergeSort();         mms.sort(inputArr);         for(int i:inputArr){             System.out.print(i);             System.out.print(" ");         }     }           public void sort(int inputArr[]) {         this.array = inputArr;         this.length = inputArr.length;         this.tempMergArr = new int[length];         doMergeSort(0, length - 1);     }       private void doMergeSort(int lowerIndex, int higherIndex) {                   if (lowerIndex < higherIndex) {             int middle = lowerIndex + (higherIndex - lowerIndex) / 2;             // Below step sorts the left side of the array             doMergeSort(lowerIndex, middle);             // Below step sorts the right side of the array             doMergeSort(middle + 1, higherIndex);             // Now merge both sides             mergeParts(lowerIndex, middle, higherIndex);         }     }       private void mergeParts(int lowerIndex, int middle, int higherIndex) {           for (int i = lowerIndex; i <= higherIndex; i++) {             tempMergArr[i] = array[i];         }         int i = lowerIndex;         int j = middle + 1;         int k = lowerIndex;         while (i <= middle && j <= higherIndex) {             if (tempMergArr[i] <= tempMergArr[j]) {                 array[k] = tempMergArr[i];                 i++;             } else {                 array[k] = tempMergArr[j];                 j++;             }             k++;         }         while (i <= middle) {             array[k] = tempMergArr[i];             k++;             i++;         }       } }

Output: 4 11 23 28 43 45 65 77 89 98