# Kastar om ordningen på elementen i listan v så att
# v[0] <= v[1] <= ... <= v[len(v)-1].
# Tidskomplexitet: O(n^2). Använder inget extra utrymme.
def insort(v):
    for j in range(1, len(v)):
    # Invariant: delvektorn v[0..j-1] består av
    # samma element som ursprungsvektorn v[0..j-1]
    # men i sorterad ordning.
        key = v[j]
        i = j - 1
        while i >= 0 and v[i] > key:
            v[i+1] = v[i]
            i -= 1
        v[i+1] = key

# Returnerar en lista med samma element som v,
# men i sorterad ordning.
# Tidskomplexitet: O(n log n). Använder n log n extra utrymme.
def mergesort(v):
    n = len(v)
    if n <= 1:
        return v
    mid = n//2
    left = mergesort(v[:mid]) # kopia
    right= mergesort(v[mid:]) # kopia
    return merge(left, right)

# Returnerar en samsorterad lista av de två sorterade
# listorna a och b.
def merge(a, b):
    v = []
    while a != [] and b != []:
        if a[0] < b[0]:
            v.append(a.pop(0))
        else:
            v.append(b.pop(0))
    return v + a + b # a or b is empty

def main():
    v = [3, 2, 1, 5, 7, 6]

    w = v[:]
    insort(w)
    print(v, w)

    w = mergesort(v)
    print(v, w)

main()