package facebook.prep.basic;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class MergeSort {

    public void sort(int[] array) {
        divideAndMerge(array, 0, array.length);
    }

    private void divideAndMerge(int[] array, int start, int end) {
        if (end - start < 2) {
            return;
        }
        int s1 = start;
        int e1 = (start + end) / 2; // Exclusive
        divideAndMerge(array, s1, e1);
        int s2 = e1;      // Inclusive
        int e2 = end;
        divideAndMerge(array, s2, e2);

        int l1 = e1 - s1;
        int l2 = e2 - s2;
        if (l1 == 0 || l2 == 0) {
            return;
        }

        // Do merge
        int[] tmp = new int[end - start];
        int i1 = 0;
        int i2 = 0;
        while (i1 + i2 < l1 + l2) {
            if (i1 == l1) {
                tmp[i1+i2] = array[s2+i2];
                i2++;
            } else if (i2 == l2) {
                tmp[i1+i2] = array[s1+i1];
                i1++;
            } else {
                if (array[s1 + i1] < array[s2 + i2]) {
                    tmp[i1 + i2] = array[s1 + i1];
                    i1++;
                } else {
                    tmp[i1 + i2] = array[s2 + i2];
                    i2++;
                }
            }
        }
        System.arraycopy(tmp, 0, array, s1, e2 - s1);
    }

    @Test
    public void testEmpty() {
        int[] array = new int[0];
        sort(array);
        Assert.assertArrayEquals(new int[0], array);
    }

    @Test
    public void test1() {
        int[] array = new int[] {4, 3, 2, 1};
        sort(array);
        int[] expected = array.clone();
        Arrays.sort(expected);
        Assert.assertArrayEquals(expected, array);
    }

    @Test
    public void test2() {
        int[] array = new int[] {4, 3, 2, 85, 2, 49, 18, 91};
        sort(array);
        int[] expected = array.clone();
        Arrays.sort(expected);
        Assert.assertArrayEquals(expected, array);
    }
}