1 public class Solution { 2     public List
     
       countSmaller(int[] nums) { 3         List
      
        result = new ArrayList<>(); 4         List
       
         record = new ArrayList<>(); 5          6         if (nums.length == 0) { 7             return result; 8         } 9         result.add(0);10         record.add(nums[nums.length - 1]);11         for (int i = nums.length - 2; i >= 0; i--) {12             int start = 0, end = result.size() - 1, mid = 0;13             while (start <= end) {14                 mid = (end - start)/2 + start;15                 if (record.get(mid) >= nums[i]) {16                     end = mid - 1;17                 } else {18                     start = mid + 1;19                 }20             }21             result.add(0, start);22             record.add(start, nums[i]);23         }24         return result;25     }26 }
       
      
     

1. This binary search is find the insertion position. Since it starts from end of array. So it must be greater and equal to mid number.

 

The merge sort method is pretty tricky