Quicksort (Ruby)

quicksort.rb

def quicksort(array, left = 0, right = nil)
  right ||= array.size - 1 # Sort the whole array be default

  # NOTE: This is subtle; we only need to perform the sorting if `left` is less
  #       than `right`
  if left < right
    index = sort(array, left, right)

    quicksort(array, left, index - 1)  # Sort left sub_array
    quicksort(array, index + 1, right) # Sort right sub_array
  end

  array
end

def sort(array, left, right)
  wall  = index = left
  pivot = array[right]

  # NOTE: This is subtle; we only iterate through if there are elements to be
  #       sorted
  while(index < right) do
    if array[index] < pivot
      # NOTE: Unsorted element found: We need to swap the `index` & `wall`
      #       elements, and increment `wall`
      array[index], array[wall] = array[wall], array[index]
      wall += 1
    end

    index += 1
  end

  # NOTE: Swap the `pivot` & `wall` elements
  array[wall], array[right] = array[right], array[wall]

  # NOTE: Return the `wall` index (so we can further divide the array for
  #       sorting)
  wall
end

puts "sorted: #{quicksort((1..10).to_a.shuffle)}"