private List<Integer> merge(List<Integer> left, List<Integer> right) {
        List<Integer> sorted = new ArrayList<>();

        int leftIdx = 0;
        int rightIdx = 0;
        for (int idx = 0; idx < left.size() + right.size(); ++idx) {
            // the only tricky part of Merge Sort is this if condition
            if ((rightIdx >= right.size())
                    || (leftIdx < left.size()) && (left.get(leftIdx) < right.get(rightIdx))) {
                sorted.add(left.get(leftIdx));
                ++leftIdx;
            } else {
                sorted.add(right.get(rightIdx));
                ++rightIdx;

                // once an element was added from the right list
                // it indicates inversion happens
                invCount += left.size() - leftIdx;
            }

            ++count;
        }

        return sorted;
    }