def mergesort(a)
 #function to mergesort an array a
 len = a.length
   
 #if array is length 1, it is already sorted
 if(len<=1) then return a end
 
 print("The current array being processed is:\n") 
 puts(a.inspect)
  
 #Dividing the array into two halves, left and right
 mid = len/2
 a_left = Array.new
 a_right = Array.new
 mid.times{ |i| a_left << a[i]}
 for i in mid..(len-1) 
    a_right << a[i]
 end
 
 print("The two halves are:\n")
 puts(a_left.inspect)
 puts(a_right.inspect)

 #Sorting each half by mergesort
 a_left_sorted = mergesort(a_left)
 a_right_sorted = mergesort(a_right)

 #Merging the sorted halves to produce the sorted array
 a_sorted = merge(a_left_sorted, a_right_sorted)
 
 print("The sorted array being returned from the current function is:\n")
 puts(a_sorted.inspect)
 #returning the sorted array
 return a_sorted
end

def merge(a_l, a_r)
 #function to merge two sorted arrays
 len1 = a_l.length
 len2 = a_r.length
 i = 0
 j = 0
 a_merged = Array.new

 #scanning through the length of both arrays, comparing the current 
 #elements in each, till one of the arrays are exhausted

 while(i< len1 and j<len2)
  if(a_l[i] < a_r[j])
    a_merged << a_l[i]
    i = i + 1
  else
    a_merged << a_r[j]
    j = j + 1
  end
 end

 #when at least one of the arrays are exhausted, the remaining array can 
 #be added as it is to produce a sorted array

 for k in j..(len2-1)
  a_merged << a_r[k]
 end
 for k in i..(len1-1)
  a_merged << a_l[k]
 end

 #returning the merged sorted array by merging two sorted sub-arrays 
 return a_merged
end
   
arr = Array[3,0,5,-1,-2,7,6,-8]

print("The unsorted array is \n") 
puts(arr.inspect)

arr_sorted = mergesort(arr)