count split inversions

#count split inversions via divide and conquer strat

def sort_and_count(array)
  mid = array.length / 2
  left = array[0...mid]
  right = array[mid..-1]
  
  if array.count <= 1
    return 0, array
  else
    x, first_sorted_array = sort_and_count(left)
    y, second_sorted_array = sort_and_count(right)
    z, merged_array = merge_and_count_split_inv(first_sorted_array,second_sorted_array)
  end
  
  return x + y + z, merged_array
end

def merge_and_count_split_inv(left,right)
  merged_array = []
  split_inv = 0  
  
  while left.size > 1 & right.size > 1
    if left[0] <= right[0]
      merged_array.push(left.shift)
    else if right[0] < left[0]
      merged_array.push(right.shift)
      split inv += left.size
    end
  end
  
  if left[0]
    merged_array.concat(left)
  elsif right[0]
    merged_array.concat(right)
  end
  
  return split_inv, merged_array
end