#!/usr/bin/ruby

# Merge sort algorithm

func merge(left, right) {

    var array = [];
    var nL = left.len;
    var nR = right.len;

    var(i=0, j=0);
    while (i<nL && j<nR) {
        array << (left[i] <= right[j] ? left[i++] : right[j++]);
    }

    array += left.ft(i);
    array += right.ft(j);

    return array;
}

func merge_sort(array { .len < 2 }) { array }

func merge_sort(array) {
    var (left, right) = @|array/2

    __FUNC__(left)
    __FUNC__(right)

    array[] = merge(left, right)...
}

var arr = [3,4,7,6,2,5,1,0].shuffle
merge_sort(arr)

assert_eq(arr, arr.sort)
say "** Test passed!"
