sort.nim

proc merge[T](a: var seq[T], b: var seq[T]): seq[T] =
    result = newSeqOfCap[T](a.len + b.len)

    while a.len != 0 and b.len != 0:
        if a[0] < b[0]:
            result.add(a[0])
            a = a[1..^1]
        else:
            result.add(b[0])
            b = b[1..^1]
    
    while a.len != 0:
        result.add(a[0])
        a = a[1..^1]
    
    while b.len != 0:
        result.add(b[0])
        b = b[1..^1]


proc sort*[T](s: seq[T]): seq[T] =
    # 1 or 0 elements.
    if len(s) <= 1:
        return s
    
    var
        leftSize = s.len div 2
        rightSize = s.len - leftSize
        leftArr = newSeqOfCap[T](leftSize)
        rightArr = newSeqOfCap[T](rightSize)

    var idx = 1
    for element in s:
        if idx <= leftSize:
            leftArr.add(element)
        else:
            rightArr.add(element)
        inc idx
    
    leftArr = sort(leftArr)
    rightArr = sort(rightArr)

    merge(leftArr, rightArr)


var l: seq[int] = @[15, 1, 2, 3, -1, 8]
echo(l.sort())