Basic merge sort

merge_sort.rb

# Basic merge sort

def merge_sort(list)
	# Return the original array if its size is 1 or less.
	return list if list.length <= 1

	# Split the array in half.
	mid = list.length / 2
	left = list[0..mid - 1]
	right = list[mid..-1]

	# Merge the halved array.
	left = merge_sort(left)
	right = merge_sort(right)
	merge(left, right)
end

def merge(left, right, merged = [])
	# While both arrays are occupied...
	while left.length > 0 && right.length > 0
		# First to items in each list are compared.
		# Then, the smaller of the two is moved into the marged list
		# and removed from the original array.
		merged << (left[0] < right[0] ? left.shift : right.shift)
	end

	# Whichever list is not empty gets combined with the merged list.
	merged += left.length == 0 ? right : left

	return merged
end

# EXAMPLE
arr = [42,31,47,7,-5,87,14,19,111,43,459,9,22,11]
puts merge_sort(arr)
# => -5 7 9 11 14 19 22 31 42 43 47 87 111 459