#algorithms

MergeSort.java

// the recursive mergesort divides an array with length N to N singlton array
// and then merge them together back to one sorted array. It's a top down approach.
// All the work of sorting is done by the merge action.
// the iterative version is however, a bottom up approach. we skip the divide step
// and iteratively call the merge action from the beginning.
// however, the indexing tuning can be a bit annoying. A goog alternative is to use
// a queue. We dequeue two arrays from the queue, merge them together and put the merged
// array back to the queue. This repeats until there's only one array in the queue, the final
// sorted one.
import java.util.Queue;
import java.util.LinkedList;
public class MergeSort{
    private class Range{
        int low;
        int high;
        public Range(int low, int high){
            this.low = low;
            this.high = high;
        }
    }
    
    public void sort(int[] nums){
        if(nums == null || nums.length <= 1) return;
        
        Queue<Range> ranges = new LinkedList<Range>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
            ranges.offer(new Range(i, i));
        }
        
        while(ranges.size() > 1){
            Range first = ranges.poll();
            Range second = ranges.poll();
            ranges.offer(merge(first, second, nums));
        }
    }
    
    private Range merge(Range first, Range second, int[] nums){
        int mergedLow = first.low < second.low ? first.low : second.low;
        int mergedHigh = first.high > second.high ? first.high : second.high;
        
        int[] tmp = new int[mergedHigh - mergedLow + 1];
        int i = first.low;
        int j = second.low;
        int k = 0;
        while(i <= first.high && j <= second.high){
            if(nums[i] < nums[j]){
                tmp[k++] = nums[i];
                i++;
            }else{
                tmp[k++] = nums[j];
                j++;
            }
        }
        if(i > first.high){
            while(j <= second.high) tmp[k++] = nums[j++];
        }
        if(j > second.high){
            while(i <= first.high) tmp[k++] = nums[i++];
        }
        // move back to num
        k = 0;
        i = mergedLow;
        while(k < tmp.length) num[i++] = tmp[k++];
        return new Range(mergedLow, mergedHigh);
    }
}