/******************************************************************************
 * This program demonstrates the Merge sort.
 * 
 * Copyright © 2021 Richard Lesh.  All rights reserved.
 *****************************************************************************/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.pureprogrammer.Utils;

public class MergeSort {

    static List<Integer> merge(final List<Integer> left, final List<Integer> right) {
        List<Integer> result = new ArrayList<>();
        int leftPtr = 0;
        int rightPtr = 0;
        final int LEFT_SIZE = left.size();
        final int RIGHT_SIZE = right.size();

        while (leftPtr < LEFT_SIZE && rightPtr < RIGHT_SIZE) {
            if (left.get(leftPtr) <= right.get(rightPtr)) {
                result.add(left.get(leftPtr));
                ++leftPtr;
            } else {
                result.add(right.get(rightPtr));
                ++rightPtr;
            }
        }

// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
        while (leftPtr < LEFT_SIZE) {
            result.add(left.get(leftPtr));
            ++leftPtr;
        }
        while (rightPtr < RIGHT_SIZE) {
            result.add(right.get(rightPtr));
            ++rightPtr;
        }
        return result;
    }

    static List<Integer> mergeSort(final List<Integer> list) {
        final int LIST_SIZE = list.size();
// Base case. A list of zero or one elements is sorted, by definition.
        if (LIST_SIZE <= 1) {
            final List<Integer> sortedList = list;
            return sortedList;
        }

//  Recursive case. First, divide the list into equal-sized sublists
//  consisting of the first half and second half of the list.
//  This assumes lists start at index 0.
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        final int HALFWAY_POINT = LIST_SIZE / 2;
        for (int i = 0; i < LIST_SIZE; ++i) {
            if (i < HALFWAY_POINT) {
                left.add(list.get(i));
            } else {
                right.add(list.get(i));
            }
        }

// Recursively sort both sublists.
        left = mergeSort(left);
        right = mergeSort(right);

// Then merge the now-sorted sublists.
        final List<Integer> result = merge(left, right);
        return result;
    }

    public static void main(String[] args) {
        if (args.length != 2) {
            System.out.println(Utils.join("", "Syntax: ", "MergeSort", " list_size max_int"));
            System.exit(1);
        }
        final int LIST_SIZE = Utils.stoiWithDefault(args[0], 10);
        final int MAX_INT = Utils.stoiWithDefault(args[1], 100);

        List<Integer> listToSort = new ArrayList<>();
        System.out.println("Random List");
        for (int i = 0; i < LIST_SIZE; ++i) {
            listToSort.add((int)(MAX_INT * Math.random()));
        }
        System.out.println(Utils.listToString(listToSort));

        listToSort = mergeSort(listToSort);

        System.out.println("Sorted List");
        System.out.println(Utils.listToString(listToSort));
    }
}