# My NlogN mergesort solution

• ``````    public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new ArrayList<>();
if(nums == null || nums.length == 0) return result;

int[] idx = new int[nums.length];
for(int i = 0; i < idx.length; i++) {
idx[i] = i;
}

helper(nums, idx, result, 0, idx.length-1);
return result;
}

void helper(int[] nums, int[] idx, List<Integer> result, int l, int r) {
if(l >= r) return;

int mid = (l + r) >>> 1;
helper(nums, idx, result, l, mid);
helper(nums, idx, result, mid+1, r);
merge(nums, idx, l, r, result);
}

void merge(int[] nums, int[] idx, int l, int r, List<Integer> result) {
int m = (l + r) >>> 1;
int i = l;
int j = m + 1;
int[] temp = new int[r - l + 1];
int k = 0;

while(i <= m) {
while(j <= r && nums[idx[i]] > nums[idx[j]]) {
temp[k++] = idx[j++];
}

int len = j - (m+1);
result.set(idx[i], result.get(idx[i]) + len);

temp[k++] = idx[i++];
}

while(j <= r) temp[k++] = idx[j++];

for(i = l; i <= r; i++) {
idx[i] = temp[i - l];
}
}
}
``````

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