package srt

func MergeSort[T any](x []T, c Comparer[T]) []T {
    if len(x) < 2 {
        return x
    }
    middle := len(x) / 2
    left := x[:middle]
    right := x[middle:]
    leftSorted := MergeSort(left, c)
    rightSorted := MergeSort(right, c)
    out := make([]T, len(x))
    for i := 0; i < len(x); i++ {
        if len(leftSorted) < 1 {
            out[i] = rightSorted[0]
            rightSorted = rightSorted[1:]
            continue
        }
        if len(rightSorted) < 1 {
            out[i] = leftSorted[0]
            leftSorted = leftSorted[1:]
            continue
        }
        if c.Less(leftSorted[0], rightSorted[0]) {
            out[i] = leftSorted[0]
            leftSorted = leftSorted[1:]
        } else {
            out[i] = rightSorted[0]
            rightSorted = rightSorted[1:]
        }
    }
    return out
}

def merge_sort(data):
    li = 0
    ri = len(data)-1
    if ri == li:
        return data
    middle = (len(data) - li) // 2
    left = data[:middle]
    right = data[middle:]
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    out = []
    for i in range(len(data)):
        if len(left_sorted) < 1:
            out.append(right_sorted[0])
            right_sorted = right_sorted[1:]
            continue
        if len(right_sorted) < 1:
            out.append(left_sorted[0])
            left_sorted = left_sorted[1:]
            continue
        if len(left_sorted) > 0 and left_sorted[0] < right_sorted[0]:
            out.append(left_sorted[0])
            left_sorted = left_sorted[1:]
        else:
            out.append(right_sorted[0])
            right_sorted = right_sorted[1:]
    return out


if __name__ == "__main__":
    data = [3,9,2, 16,38, 25, 91,6, 34,8, 59, 62, 7, 5, 46]
    out = merge_sort(data)
    print(out)