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


// 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()