// ------------------------------------------------------------------
//
//	What:
//
// 		Main function that performs merge_sort
//
// Parameters:
//
//		t an array of integers
//
// ------------------------------------------------------------------
proc merge_sort( t is array[1..n] of int )

	// start recursive split
	split(t, 1, n)
	
end proc

// ==================================================================
//
//	What:
//
// 		Recursively split the initial array in two subarrays
//
// Parameters:
//
//		a is the minimum index of array t
// 		b is the maximum index of array t
//
// ==================================================================
proc split( t is array[1..n] of int; a, b  are int )

	var size = b - a + 1
	
	if size = 1 then
	
	    exit proc
	    
	if size = 2 then
	
	    if t[a] > t[a+1] then
	    	swap( t[a], t[a+1] )
	    end if
	    
	else
		// m is the middle index
		var m = (a + b + 1) / 2
		split( t, a, m-1 )
		split( t, m, b )
		merge( t, a, m, b )	
	end if
	
end proc

// ==================================================================
//
// 	What:
// 
// 		Merge two subarrays into a one array and copy result to 
// 		the initial array
//
// 	Parameters:
//
//		t an array of integers
//		a is the minimum index of array t
//		m is the middle index of array t
// 		b is the maximum index of array t
//	
// ==================================================================
proc merge( t is array[1..n] of int; a, m, b are int ) {

	// array which is the result of the merge of arrays
	// from [a..m] and [m+1..b]
	var tmp is array[1..b-a+1] of int
	var i = a
	var j = m
	
	// copy back data following order into tmp
	while (i < m) and(j < b+1) do
		if t[i] < t[j] then
			tmp[k] = t[i]
			i = i + 1
			k = k + 1
		else if t[j] < t[i] then
			tmp[k] = t[j]
			j = j + 1
			k = k + 1
		else
			tmp[k] = t[i]
			i = i + 1
			k = k + 1
			tmp[k] = t[j]
			j = j + 1
			k = k + 1
		end if
	end while

	while i < m do
		tmp[k] = t[i]
		i = i + 1
		k = k + 1
	end while

	while j < b+1 do
		tmp[k] = t[i2]
		j = j + 1
		k = k + 1
	end while

	// copy tmp to t[a]
	t[a..b] = tmp[1..t.size()]
	
end proc