def merge(arr, temp_arr, left, mid, right)
    i = left    # Starting index for left subarray
    j = mid + 1 # Starting index for right subarray
    k = left    # Starting index for sorted subarray
    inv_count = 0
  
    while i <= mid && j <= right
      if arr[i] <= arr[j]
        temp_arr[k] = arr[i]
        i += 1
      else
        temp_arr[k] = arr[j]
        inv_count += (mid - i + 1) # Count inversions
        j += 1
      end
      k += 1
    end
  
    while i <= mid
      temp_arr[k] = arr[i]
      i += 1
      k += 1
    end
  
    while j <= right
      temp_arr[k] = arr[j]
      j += 1
      k += 1
    end
  
    (left..right).each do |idx|
      arr[idx] = temp_arr[idx]
    end
  
    inv_count
  end
  
  def merge_sort(arr, temp_arr, left, right)
    inv_count = 0
    if left < right
      mid = (left + right) / 2
  
      inv_count += merge_sort(arr, temp_arr, left, mid)
      inv_count += merge_sort(arr, temp_arr, mid + 1, right)
  
      inv_count += merge(arr, temp_arr, left, mid, right)
    end
    inv_count
  end
  
  # Wrapper to call merge sort
  def count_inversions(arr)
    temp_arr = Array.new(arr.length)
    merge_sort(arr, temp_arr, 0, arr.length - 1)
  end


def insertionSort(arr)
    count = count_inversions(arr)
end