Comparison count in Qsort algorithm

qsort_comp.rb

class Integer
  def odd?
    % 2 == 0 
  end
end

def middle_index(input)
  size = input.size
  if size.odd?
    size/2
  else
    size/2-1
  end
end

def pivot_index(list, first, middle, last)
  list[middle], list[first] = list[first], list[middle] if list[first] > list[middle]

  list[first], list[last] = list[last], list[first] if list[first] > list[last]
  
  list[middle], list[last] = list[last], list[middle] if list[middle] > list[last]
  
  middle
end

$comparisons = 0

def quicksort(list, p, r)
  if p < r
    q = partition(list, p, r)
    quicksort(list, p, q-1)
    quicksort(list, q+1, r)
  end
end

def partition(list, p, r)
  pivot_index = pivot_index(list, p, middle_index(list[p..r]), r)
  
  #pivot_index = r
  pivot = list[pivot_index]
  
  list[p], list[pivot_index] = list[pivot_index], list[p]
  
  $comparisons += (r-p)
  
  i = p + 1
  (p + 1).upto(r) do |j|
    if list[j] < pivot
      list[i], list[j] = list[j], list[i]
      i += 1
    end
  end
  i -= 1
  list[i], list[p] = list[p], list[i]
  
  i
end

input = []
File.open('input', 'r') do |file|
  while line = file.gets
    input << line.chomp.to_i
  end
end

quicksort(input, 0, input.size-1)
p $comparisons