Merge Sort Implementation

Concept
把array拆分成最小單位，再一一合併。

input: int array in an arbitrary order
output: int array in ascending order

[10, 22, 3, 34, 9, 2]
[10, 22, 3] [34, 9, 2]
[10] [22, 3] [34] [9, 2]
[10] [22] [3] [34] [9] [2]

[10] [3, 22] [34] [2, 9]
[3, 10, 22] [2, 9, 34]
[2, 3, 9, 10, 22, 34]

Pseudocode

main(): declare array, and call mergeSort(array, 0, len-1)

mergeSort(arr, lower, higher):
    if(lower < higher)
        用middle把arr拆成兩半
        mergeSort(左半)
        mergeSort(右半)
        merge(arr, lower, middle, higher)

merge(arr, lower, middle, higher):
    把arr分成左右兩邊
    int[] L
    int[] R
    並把L,R中的element都放好

    int  i, j, k分別track L, R, arr
    while(i和j都在L和R的長度範圍之內)
        把L[i]和R[j]中較小的放入arr[k]

    如果L有剩，把剩下的放入arr
    如果R有剩，把剩下的放入arr

Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution{
    public static void main (String[] args) {

        int[] arr = {45,23,11,89,77,98,4,28,65,43};
        mergeSort(arr);

           for(int i : arr){
               System.out.print(i+" ");
           }
    }

    public static void mergeSort(int[] arr){
        int len = arr.length;
        mergeSort(arr, 0, len-1);
    }

    private static void mergeSort(int[] arr, int lower, int higher){
        if(lower < higher){
            int middle = lower + (higher - lower)/2;
            mergeSort(arr, lower, middle);
            mergeSort(arr, middle + 1, higher);
            merge(arr, lower, middle, higher);
        }
    }

    private static void merge(int[] arr, int lower, int middle, int higher){
        int len1 = middle - lower +1;
        int len2 = higher - middle;

        int[] L = new int[len1];
        int[] R = new int[len2];

        for(int i=0; i<len1; i++){
            L[i] = arr[lower+i];
        }
        for(int j=0; j<len2; j++){
            R[j] = arr[middle + 1 + j];
        }

        //initial index to merge
        int i=0, j=0;
        int k = lower;
        while(i < len1 && j < len2){
            if(L[i] <= R[j]){
                arr[k] = L[i];
                i++;
            }else{
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        //merge the remains
        while(i < len1){
            arr[k] = L[i];
            i++; k++;
        }

        while(j < len2){
            arr[k] = R[j];
            j++; k++;
        }        
    }
}