quick sort

sort.rb

def partition(list, low, high)
  i = low
  j = high + 1
  base_num = list[low]

  while true
    i += 1
    while list[i] < base_num
      if i == high
        break
      end
      i += 1
    end

    j -= 1
    while list[j] > base_num
      if j == low
        break
      end
      j -= 1
    end

    if i >= j
      break
    end

    temp = list[i]
    list[i] = list[j]
    list[j] = temp

  end

  temp = list[low]
  list[low] = list[j]
  list[j] = temp

  j

end

def quick_sort(list, left, right)

  if left >= right
    return
  end

  base_index = partition(list, left, right)

  quick_sort(list, left, base_index - 1)

  quick_sort(list, base_index + 1, right)

  list

end

def quick_sort_3way(list, low, high)

  if high <= low
    return
  end

  less_to = low
  great_to = high
  i = low + 1

  base_num = list[low]

  while i <= great_to
    if list[i] < base_num
      temp = list[i]
      list[i] = list[less_to]
      list[less_to] = temp

      i += 1
      less_to += 1
    elsif list[i] > base_num
      temp = list[i]
      list[i] = list[great_to]
      list[great_to] = temp

      great_to -= 1
    else
      i += 1
    end
  end

  quick_sort_3way(list, low, less_to - 1)
  quick_sort_3way(list, great_to + 1, high)

  list

end