Algorithm: Essence of Merge Sort

Merge Sort

Actually I think merge sort is a very beautiful algorithm, perfectly reflect the philosophy of computer world: divide and concur.

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{5,5,2,7,5,8,3,2,1,9,4,2,5,6,7,8,3,2};
        process(arr, 0, arr.length - 1);
    }
    
    private static void process(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + (right - left) / 2; // find the upper middle
        
        process(arr, left, mid);
        process(arr, mid + 1, right);
        
        // at this point, we can assume arr[left ... mid] & arr[mid + 1 ... right] is sorted
        
        merge(arr, left, mid, right);
    } 
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int l = left, r = mid + 1, cur = 0;
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                temp[cur++] = arr[l++];
            } else {
                temp[cur++] = arr[r++];
            }
        }
        
        while(l <= mid) {
            temp[cur++] = arr[l++];
        }
        
        while(r <= right) {
            temp[cur++] = arr[r++];
        }
        
        // write sorted arr back to original arr
        l = left, cur = 0;
        while (cur < temp.length) {
            arr[l++] = temp[cur++];
        }
    }
}

The essence of this algorithm is it can keep the previous sorting result, or to be general, it can keep previous comparison result,

Also before merging, the relative positition between two elements are not changed.

which is a great leverage.

Let take this question as example:

the definition of smallNumber: 
for a given number in arr, all number smaller than it and on its left is called smallNumber

get the sum of all smallNumber in this array.

example: [1,3,2]

the small numbers of 1: []
the small numbers of 3: [1]
the small numbers of 2: [1]

then the smallNumberSum = 2

public class SmallNumberSum {
    public static void main(String[] args) {
        // test code
    }
    
    private static int sumSmallNumber(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) + 1;
        
        int leftSum = sumSmallNumber(arr, left, mid);
        int rightSum = sumSmallNumber(arr, mid + 1, right);
        
        return leftSum + rightSum + merge(arr, left, mid, right);
    }
    
    private static int merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int sum = 0;
        
        int l = left, r = mid + 1, cur = 0;
        
        while(l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                // find smallNumber
                sum += arr[l] * (right - r + 1);
                temp[cur++] = arr[l++];
            } else {
                temp[cur++] = arr[r++];
            }
        }
        
        while(l <= mid) {
            temp[cur++] = arr[l++];
        }
        
        while (r <= right) {
            temp[cur++] = arr[r++];
        }
        
        l = left;
        cur = 0;
        
        while(cur < temp.length) {
            arr[l++] = temp[cur++];
        }
        
        return sum;
    }
}