`` Merge Sort
`` Public Domain
`` available with other algorithms at: www.scriptol.org


// Merge: given a and b assumed to be sorted, returns a merged array

array merge(array a, array b)
    int n = a.size()
    int m = b.size()
    int top = n + m
    array result
    int i = 0, j = 0

    while top > 0  

        if i >= n
            result.push(b[j])
            j + 1
            continue
        /if    
        if j >= m
            result.push(a[i])
            i + 1
            continue
        /if    

        if a[i] < b[j]
            result.push(a[i])
            i + 1
        else
            result.push(b[j])
            j + 1
        /if
    
    let top - 1

return result


// Sort: returns a sorted copy of array a

array mergesort(array a)
    int n = a.size()
    if n < 2 return a

    int half = n / 2
    array first_half = mergesort(a[ .. half - 1])
    array second_half = mergesort(a[half .. ])
    
return merge(first_half, second_half)

array x = array( 3, 45, 5, 7, 65, 235, 9, 66, 30, 2)


x = mergesort(x)
x.display()