Merge sort

divide and conquer: left, right, count values while merging left and right
Merge sort code
http://www.jiuzhang.com/solutions/reversepairs/
private int merge(int[] A, int start, int mid, int end) {
int[] temp = new int[A.length];
int leftIndex = start;
int rightIndex = mid + 1;
int index = start;
int sum = 0;
while (leftIndex <= mid && rightIndex <= end) {
if (A[leftIndex] <= A[rightIndex]) {
temp[index++] = A[leftIndex++];
} else {
temp[index++] = A[rightIndex++];
sum += mid  leftIndex + 1;
}
}
while (leftIndex <= mid) {
temp[index++] = A[leftIndex++];
}
while (rightIndex <= end) {
temp[index++] = A[rightIndex++];
}
for (int i = start; i <= end; i++) {
A[i] = temp[i];
}
return sum;
}
LeetCode 493  Reverse Pairs

Merge sort
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (es)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j(mid+1);
}
Arrays.sort(nums, s, e+1);
return cnt;
}

build the Binary Search Tree from right to left and search the partially built tree with nums[i]/2.0
class Node{
int val, less = 0, same = 1;//less: number of nodes that less than this node.val
Node left, right;
}
LeetCode 327  Count of Range Sum
return the number of range sums that lie in [lower, upper] inclusive.

merge sort
 presum: sum[i..j]

Binary search tree
56 private int rangeSize(TreeNode root, long lower, long upper) {
57 int total = root.count + root.leftSize + root.rightSize;
58 int smaller = countSmaller(root, lower); // Exclude everything smaller than lower
59 int larger = countLarger(root, upper); // Exclude everything larger than upper
60 return total  smaller  larger;
61 }
Count Inversions in an array
LeetCode 315  Count of Smaller Numbers After Self
https://discuss.leetcode.com/topic/31554/11msjavasolutionusingmergesortwithexplanation
https://discuss.leetcode.com/topic/31162/mergesortsolution/12
int[] count;
public List countSmaller(int[] nums) {
List res = new ArrayList();
count = new int[nums.length];
int[] indexes = new int[nums.length];
for(int i = 0; i < nums.length; i++){
indexes[i] = i;
}
mergesort(nums, indexes, 0, nums.length  1);
for(int i = 0; i < count.length; i++){
res.add(count[i]);
}
return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
if(end <= start){
return;
}
int mid = (start + end) / 2;
mergesort(nums, indexes, start, mid);
mergesort(nums, indexes, mid + 1, end);
merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
int mid = (start + end) / 2;
int left_index = start;
int right_index = mid+1;
int rightcount = 0;
int[] new_indexes = new int[end  start + 1];
int sort_index = 0;
while(left_index <= mid && right_index <= end){
if(nums[indexes[right_index]] < nums[indexes[left_index]]){
new_indexes[sort_index] = indexes[right_index];
rightcount++;
right_index++;
}else{
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
}
sort_index++;
}
while(left_index <= mid){
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
sort_index++;
}
while(right_index <= end){
new_indexes[sort_index++] = indexes[right_index++];
}
for(int i = start; i <= end; i++){
indexes[i] = new_indexes[i  start];
}
}

binary search tree
TODO
Max Surpasser
LeetCode 327  Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [2, 5, 1], lower = 2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: 2, 1, 2.
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n + 1];
for (int i = 0; i < n; ++i)
sums[i + 1] = sums[i] + nums[i];
return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}
private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
if (end  start <= 1) return 0;
int mid = (start + end) / 2;
int count = countWhileMergeSort(sums, start, mid, lower, upper)
+ countWhileMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
long[] cache = new long[end  start];
for (int i = start, r = 0; i < mid; ++i, ++r) {
while (k < end && sums[k]  sums[i] < lower) k++;
while (j < end && sums[j]  sums[i] <= upper) j++;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
count += j  k;
}
System.arraycopy(cache, 0, sums, start, t  start);
return count;
}
Count Inversions in an array
Count pairs in an array that hold i*arr[i] > j*arr[j]
Find a permutation that causes worst case of Merge Sort
LeetCode 148  Sort LinkedList
 fake head ListNode fakehead = new ListNode(1);
X. How to merge
Maximum Sum Path in Two Arrays
We can switch from one array to another array only at common elements.
http://www.geeksforgeeks.org/maximumsumpathacrosstwoarrays/
if (ar1[i] < ar2[j])
sum1 += ar1[i++];
// Add elements of ar2[] to sum2
else if (ar1[i] > ar2[j])
sum2 += ar2[j++];
X. K Sorted List
 PriorityQueue
LeetCode 632  Smallest Range
Find the smallest range that includes at least one number from each of the klists.

PriorityQueue
LeetCode  Merge k Sorted Lists
Merge K Sorted Iterators  Linkedin
public class IntIter {
int next;
Iterator
iter;
}