Count of smaller numbers after self (MergeSort) - Teeeeeebag/LeetCode GitHub Wiki

class Tuple{
    public int val, pos, cnt;
    public Tuple(int v, int p){
        this.val = v;
        this.pos = p;
        cnt = 0;
    }
}
public class Solution {
    private void mergeSort(Tuple[] tpls, int s, int e){
        if(s>=e){
            return;
        }
        int mid = s + (e-s)/2;
        mergeSort(tpls, s, mid);
        mergeSort(tpls, mid+1, e);
        //merge
        Tuple[] tmp = new Tuple[e-s+1];
        int p1 = s, p2 = mid+1, p = 0;
        while (p1 <= mid || p2 <=e){
            if (p2 > e || (p1<=mid && tpls[p1].val  <= tpls[p2].val)){
                tpls[p1].cnt += p2-mid-1;
                tmp[p++] = tpls[p1++];
            } else {
                tmp[p++] = tpls[p2++];
            }
        }
        System.arraycopy(tmp, 0, tpls, s, e-s+1);
    }
    public List<Integer> countSmaller(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>();
        if(nums.length < 1){
            return res;
        }
        Tuple[] tuples = new Tuple[nums.length];
        for (int i=0; i<nums.length; ++i){
            tuples[i] = new Tuple(nums[i], i);
            res.add(0);
        }
        mergeSort(tuples, 0, tuples.length-1);
        for (int i=0; i<tuples.length; ++i){
            res.set(tuples[i].pos, tuples[i].cnt);
        }
        return res;
    }
}