Yet another clear Java merge sort solution (75ms)


  • 0
    J

    I believe mixing counting and merging in one loop makes spaghetti code, and it won't necessarily increase performance, as the counting should be run much less than the merging.
    Once the logic is separated into their own loop, the code becomes much clearer.

    public class Solution {
        private int mergeSort(int[] nums, int[] aux, int l, int r) {
            if (l >= r) return 0;
            int m = (l + r) >> 1;
            int res = mergeSort(nums, aux, l, m) + mergeSort(nums, aux, m + 1, r);
            for (int i = l; i <= r; i++) aux[i] = nums[i];
            int i = l;
            int j = m + 1;
            while (j <= r && i <= m) {
                if ((aux[i] >> 1) + (aux[i] & 1) > aux[j]) {
                    res += m - i + 1;
                    j++;
                } else i++;
            }
            i = l;
            j = m + 1;
            int p = l;
            while (j <= r && i <= m) nums[p++] = aux[i] <= aux[j] ? aux[i++] : aux[j++];
            while (j <= r) nums[p++] = aux[j++];
            while (i <= m) nums[p++] = aux[i++];
            return res;
        }
        public int reversePairs(int[] nums) {
            int aux[] = new int[nums.length];
            return mergeSort(nums, aux, 0, nums.length - 1);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.