Alg.9 Merge Sort

From algoexpert.io

For the Merge Sort, it also uses the conception “Divide and Conquer”. We simply divide the original arrays evenly recursively, then merge them. So, in Merge Sort algorithm, the time and space complexity are pretty stable.

Here is the code implementation:

public static int[] mergeSort(int[] array) {
    
        if (array.length <= 1) return array;
        
        int[] leftSubArray = Arrays.copyOfRange(array, 0, array.length / 2);
        int[] rightSubArray = Arrays.copyOfRange(array, array.length / 2, array.length);
        
    return mergeTwoArrays(mergeSort(leftSubArray), mergeSort(rightSubArray));
  }
    
    private static int[] mergeTwoArrays(int[] arr1, int[] arr2) {
        int[] ans = new int[arr1.length + arr2.length];
        int i = 0, j = 0, k = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] <= arr2[j]) ans[k++] = arr1[i++];
            else ans[k++] = arr2[j++];
        }
    
        while (i < arr1.length) ans[k++] = arr1[i++];
        
        while (j < arr2.length) ans[k++] = arr2[j++];
        
        return ans;
    }

Time complexity: O(logn); Space complexity: O(logn)

Donate