imp "@oak/list.it";
imp "@oak/time.it";
imp "@random/lib.it";

use oak;

fun MergeImpl(
    source List, 
    target List,
    source_offset Int,
    target_offset Int,
    left_run_length Int, 
    right_run_length Int
) {
    var left_index = source_offset;
    var left_index_bound = left_index + left_run_length;
    var right_index = left_index_bound;
    var right_index_bound = right_index + right_run_length;

    while left_index != left_index_bound & right_index != right_index_bound {
        if source[right_index] < source[left_index] {
            target[target_offset] = source[right_index];
            right_index += 1;
        } else {
            target[target_offset] = source[left_index];
            left_index += 1;
        }
            
        target_offset += 1;
    }

    while left_index != left_index_bound {
        target[target_offset] = source[left_index];
        target_offset += 1;
        left_index += 1;
    }

    while right_index != right_index_bound {
        target[target_offset] = source[right_index];
        target_offset += 1;
        right_index += 1;
    }
}

fun SortImpl(
    target List,
    source List, 
    target_offset Int,
    source_offset Int,
    range_len Int
) {

    if range_len < 2 {
        ret;
    }

    var middle = range_len / 2;

    SortImpl(
        ref source,
        ref target,
        source_offset,
        target_offset,
        middle
    );

    SortImpl(
        ref source,
        ref target,
        source_offset + middle,
        target_offset + middle,
        range_len - middle
    );

    MergeImpl(
        ref source,
        ref target,
        source_offset,
        target_offset,
        middle,
        range_len - middle
    );
}

`<doc>
Sorts the input list starting from start index (inclusive) and
until the end index (exclusive) using the merge sort.
</doc>`
fun MergeSort(list List, start Int = 0, end Int or Null = null) {
    SortImpl(
        ref list, 
        ref buffer,
        start,
        0,
        range_len
    );
} 

`<doc>
Sorts the input list starting from start index (inclusive) and
until the end index (exclusive) using the merge sort.
If no bounds are give the whole list will be sorted.
</doc>`
fun MergeSort(list List, start Int = 0, end Int or Null = null) {
    if end == null {
        end = Len(list);
    }

    var range_len = end - start;

    if range_len < 2 {
        ret;
    }

    var buffer = list[start..end];

    SortImpl(
        ref list, 
        ref buffer,
        start,
        0,
        range_len
    );
}

fun IsSorted(list List) Bool {
    var i = 1;
    var len = Len(list);
    var prev = list[0];
    while i < len {
        if prev > list[i] {
            ret false;
        }
        prev = list[i];
        i += 1;
    }
    ret true;
}

var time = time::Now();

var dataset = random::RandomIntDataset(20000);
MergeSort(ref dataset);
Print(dataset);

Print(time::FormatTime(time::Elapsed(time)));

Print(Format("is sorted: {}", IsSorted(dataset)));