Easy Java merge sort with explanation


  • 0
    C

    Let's divide array to two parts - left and right. If each num from right part is counted and sorted,
    it's straightforward to do count for each num from left part. Just iterate each from left part and compare with right part.

    So the idea looks like below steps :
    
    1. count each number from right part and sort right part.
    2. count each number from left part. As right part is sorted, we can do binary search to find how many number from right part
      are less than it. Then sort left part.
    3. Left and right part are sorted, merge them.
    public List<Integer> countSmaller(int[] nums) {
          int[] count = new int[nums.length];
          countAndSort(nums, 0, nums.length, count);
    
          List<Integer> list = new ArrayList<>();
          for (int i : count) {
              list.add(i);
          }
          return list;
     }
    
    private void countAndSort(int[] nums, int begin, int end, int[] count) {
        if (end - 1 <= begin) {
            return;
        }
    
        int mi = (begin + end)/2;
        countAndSort(nums, mi, end, count);
    
        for (int i = begin; i < mi; i++) {
            count[i] += binarySearch(nums, mi, end, nums[i]) - mi;
        }
    
        countAndSort(nums, begin, mi, count);
        mergeArrays(nums, begin, mi, end);
    }
    
    private void mergeArrays(int[] nums, int begin, int mi, int end) {
        int i = begin;
        int j = mi;
        int[] temp = new int[end];
        int k = 0;
    
        while (i < mi && j < end) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
    
        while (i < mi) {
            temp[k++] = nums[i++];
        }
    
        while (j < end) {
            temp[k++] = nums[j++];
        }
    
        k = 0;
        for (int l = begin; l < end; l++) {
            nums[l] = temp[k++];
        }
    }
    
    private int binarySearch(int[] nums, int lo, int hi, int target) {
        while (lo < hi) {
            int mi = lo + (hi - lo)/2;
    
            if (target > nums[mi]) {
                lo = mi + 1;
            } else {
                hi = mi;
            }
        }
    
        return lo;
    }

Log in to reply
 

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