Interview Question for Adsense at Google:

The Java version:

    public static ArrayList merge_sort_method(ArrayList input_list){
        ArrayList output_list = new ArrayList();
        int n = input_list.size();
        if(n == 1){
            return input_list;
        }
        else{
            //recursively sort
            int input_1_length = 0;
            int input_2_length = 0;
            if(n%2 == 0){
                input_1_length = n/2;
             }
            else
            {
                input_1_length = n/((int)2)+1;
            }
            input_2_length = n-input_1_length;

            ArrayList input_list_1 = new ArrayList(input_1_length);
            ArrayList input_list_2 = new ArrayList(input_2_length);
            for(int i = 0; i < input_1_length; i++){
                input_list_1.add(input_list.get(i));
            }
            for(int i = 0; i < input_2_length; i++){
                input_list_2.add(input_list.get(input_1_length+i));
            }

            ArrayList output_1 = merge_sort_method(input_list_1);
            ArrayList output_2 = merge_sort_method(input_list_2);

            //Merge
            int i = 0;
            int j = 0;
            while(i < output_1.size() && j < output_2.size()){
                if(((Integer)output_1.get(i)).intValue() <= ((Integer)output_2.get(j)).intValue()){
                    output_list.add(output_1.get(i));
                    i++;
                }
                else{
                    output_list.add(output_2.get(j));
                    j++;
                }
            }
            if(i < output_1.size()){
                for(; i < output_1.size(); i++){
                    output_list.add(output_1.get(i));
                }
            }

            if(j < output_2.size()){
                for(; j < output_2.size(); j++){
                    output_list.add(output_2.get(j));
                }
            }
        }

        return output_list;
    }