Divide and Conquer

In this section, we will implement merge sort which utilised divide and conquer algorithm.

We first define the sort function which divide the problem until the smallest subproblem then merge it.

  public static void sort(int[] arr, int l, int r){
        if (l<r){
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr, m+1, r);

            merge(arr, l, m,  r);
        }
    }

Then we will define the merge function which replace the arr in place.

  public static void merge(int[] arr, int l, int m, int r){
        int sizeLeftTemp = m - l + 1;
        int sizeRightTemp = r - m;

        int LeftTemp[] = new int[sizeLeftTemp];
        int RightTemp[] = new int[sizeRightTemp];

        //copy to left temp and right temp from arr
        for (int i = 0; i < sizeLeftTemp; ++i)
            LeftTemp[i] = arr[l + i];
        for (int j = 0; j < sizeRightTemp; ++j)
            RightTemp[j] = arr[m + 1 + j];

        int i = 0, j = 0;

        int arrIndex = l;

        //compare Lefttemp and rightTemp and replace arr[arrIndex]
        while (i < sizeLeftTemp && j < sizeRightTemp) {
            if (LeftTemp[i] <= RightTemp[j]) {
                arr[arrIndex] = LeftTemp[i];
                i++;
            }
            else {
                arr[arrIndex] = RightTemp[j];
                j++;
            }
            arrIndex++;
        }

        //copy the rest
        while (i < sizeLeftTemp) {
            arr[arrIndex] = LeftTemp[i];
            i++;
            arrIndex++;
        }

        while (j < sizeRightTemp) {
            arr[arrIndex] = RightTemp[j];
            j++;
            arrIndex++;
        }
    }

You can try to run the code here:

Run on jdoodle