package com.blogspot.groglogs.mergesort;

public class Mergesort {

    //need to pass the res array as input since we are pass by value!
    public static int[] merge(int[] res, int[] left, int[] right){
        int left_idx = 0, right_idx = 0, res_idx = 0;

        if(left == null || right == null || left.length == 0 || right.length == 0) return null;

        //scan both left and right until we reach either end
        //CAUTION: the indexes are the easiest part to screw up!
        //DOUBLE CAUTION: we must loop BOTH arrays at the same time! We don't know how are they sorted!
        while(left_idx < left.length && right_idx < right.length){
            //order the elements while keeping track of the indexes
            //if left is smaller than right, copy left, increase left, increase result
            if(left[left_idx] <= right[right_idx]){
                res[res_idx] = left[left_idx];
                left_idx++;
                res_idx++;
            }
            //otherwise, copy right, increase right, increase result
            else{
                res[res_idx] = right[right_idx];
                right_idx++;
                res_idx++;
            }
        }

        //we are still not finished, maybe we have some elements still in left or right, copy them as well
        while(left_idx < left.length){
            res[res_idx] = left[left_idx];
            res_idx++;
            left_idx++;
        }

        while(right_idx < right.length){
            res[res_idx] = right[right_idx];
            res_idx++;
            right_idx++;
        }

        return res;

    }

    public static int[] sort(int[] list){
        int[] left, right;

        if(list == null || list.length == 0) return null;

        //our base case, a list of a single element is already sorted
        if(list.length == 1) return list;

        //split array in two halves
        //fun fact: Math.floor returns a double
        left  = new int[list.length - (int)Math.floor(list.length / 2)];
        right = new int[list.length - left.length];

        //copy the elements in the two arrays left and right
        for(int i = 0; i < left.length; i++){
            left[i] = list[i];
        }

        for(int i = left.length, j = 0; i < list.length; i++, j++){
            right[j] = list[i];
        }

        //sort both parts separately
        sort(left);
        sort(right);

        //then put everything together at each step
        return merge(list, left, right);
    }

}