merge_sort.rb

# *****************************************************************************
# Functions:
# *****************************************************************************


# runs the full mergesort algorithm on the inputted array
def mergesort(inarr)
	results = []
	arrsize = inarr.size
	i = 0
	counter = 0

	# run the merge on each pair of lists until we have one remaining list
	while i < arrsize

		if i == arrsize - 1 # we're at a dangling odd number
			results << inarr[i]
			i += 1
		else
			results << mergelists(inarr[i], inarr[i+1])
			i += 2
		end
	end

	# If we haven't reduced ourselves to a list of 1, it's time to do it again
	if results.size > 1
		mergesort(results)
	else
		return results[0]
	end
end


# inputs two sorted arrays and merges into one sorted array, which is returned
def mergelists(arr1, arr2)
	size1 = arr1.size
	size2 = arr2.size
	totalsize = size1 + size2

	results = []
	i = 0
	j = 0

	# continuously compare the first (smallest) elements of each array and push that into results
	until results.size == totalsize

		# compare the first elements, place the smaller of the two in the results array
		if i == size1 # we've used up arr1
			results << arr2[j]
			j += 1
		elsif j == size2 # we've used up arr2
			results << arr1[i]
			i += 1
		elsif arr1[i] < arr2[j]
			results << arr1[i]
			i += 1
		else 
			results << arr2[j]
			j += 1
		end
	end
	results
end


# turns each element of an array into an array itself
def explodelist(arr)
	arr.each_slice(1).to_a
end



# *****************************************************************************
# Grab the user input, explode the list of words, and send it over to mergesort
# *****************************************************************************
arr = []
s = String.new

until s == "\n"
	if s.size == 0 
		puts "Give me a word.  Press <enter> on a blank line to see the sorted results"
	else
		puts "Give me another word or press enter!"
	end
	s = gets
	arr << s.chomp if s.chomp != ''
end

puts "Your sorted array is:"
puts mergesort(explodelist(arr)).inspect