class MergeSort

	def mergeSort(list, low, high)
		return if low >= high
		mid = (low+high)/2
		mergeSort(list, low, mid)
		mergeSort(list, mid+1, high)
		merge(list, low, mid, high)
	end

	def merge(list, low, mid, high)
		arr = Array.new(high-low+1)
		i=low
		j=mid+1
		k=0

		while (i<=mid && j<=high) do
			if list[i] < list[j] then
				arr[k] = list[i]
				i+=1	
			else
				arr[k] = list[j]
				j+=1	
			end
			k+=1
		end
		#----------------------------------------------------------------
		#want to do above while loop as follow: 
		# (low..mid, mid+1..high).each do |p,q| 
		# 	if list[i] < list[j] then
		# 		arr[k] = list[i]
		# 		i+=1	
		# 	else
		# 		arr[k] = list[j]
		# 		j+=1	
		# 	end
		# 	k+=1
		# end
		#or if it can be cut to lesser number of lines, then much better :)
		#----------------------------------------------------------------

		if i<=mid then 
			(list[i..mid]).each do |e|
				arr[k]=e
				k+=1
			end
		elsif j<=high
			(list[j..high]).each do |e|
				arr[k]=e
				k+=1	
			end
		end
		
		s=0
		(low..high).each do |e| 
			list[e] = arr[s]
			s+=1
		end
		
		#puts list[low..high] 
	end
end

sort=MergeSort.new
list = [7,6,5,4,3,2,1]
sort.mergeSort(list,0,list.length-1)
puts list