quick_sort.rb

# Quick Sort - Runtime: Average O(n log(n)), Worst O(n^2), Memory O(log(n))

def quick_sort(arr, left, right)
  index = partition(arr, left, right)
  if left > index - 1
    quick_sort(arr, left, index - 1)
  end
  if index < right
    quick_sort(arr, index, right)
  end
end

def partition(arr, left, right)
  pivot = arr[(left+right)/2]
  while left <= right
    while arr[left] < arr[index]
      left += 1
    end
    while arr[right] > arr[index]
      right -=1 
    end
    if left <= right
      arr[left], arr[right] = arr[right], arr[left]
      left += 1
      right -=1
    end
  end
  return left 
end