I put together this implementation after playing around with various partitioning- and pivot-strategies, and it runs fine. I wrote this off a version which seemed a bit different from the majority of implementations, so I'm curious on what you guys think. It works and handles duplicates.

def quicksort(a, min=0, max=a.length-1)
  if min < max
    index = partition(a, min, max)
    quicksort(a, min, index-1)
    quicksort(a, index+1, max)

def partition(a, l, r)

  piv = a[m]
  a[m], a[r] = a[r], a[m]

  cur = l
  for i in l..r-1

    if a[i] <= piv
      a[i], a[cur] = a[cur], a[i]
  a[cur], a[r] = a[r], a[cur]

  return cur

  • \$\begingroup\$ It's amusing just how terse Quicksort can be in Ruby. For a functional (that is, not in-place) version of Quicksort that is just a few lines, see this page on Ward's wiki \$\endgroup\$ Mar 9, 2014 at 10:23

2 Answers 2


You code looks nice, my main problem with it is naming:

Don't use single letters as member names, unless they are trivial. I couldn't figure out what l and r stand for until I read your code a couple of times (length? range?).

Even more so, don't ever use the letter l as a variable name - it is much too similar to 1, and is notoriously known to obfuscate code.

Don't re-use too familiar names for different purposes - partition is a well known method in ruby enumerables. Using this name for your code, especially when it involves arrays is very confusing. Don't do that. Call it reorder_partition or pivot_partition.

Expressiveness goes a long way - a[l], a[r] = a[r], a[l] works perfectly, but is hard to read, a much more readable way would be if you had a helper method swap(a, l, r). Even better might look to implement it into Array a.swap!(l, r)

Use the power of ruby - instead of l..r-1, use non-inclusive range operator - l...r

So, my version may look a little more verbose, but I believe it is much more readable. It did teach me a lot about quicksort :-)

def quicksort(array, min=0, max=array.length-1)
  if min < max
    index = reorder_partition(array, min, max)
    quicksort(array, min, index-1)
    quicksort(array, index+1, max)

def reorder_partition(array, left_index, right_index)
  middle_index = (left_index + right_index)/2
  pivot_value = array[middle_index]

  array.swap!(middle_index, right_index)

  less_array_pointer = left_index

  (left_index...right_index).each do |greater_array_pointer|
    if array[greater_array_pointer] <= pivot_value
      array.swap!(greater_array_pointer, less_array_pointer)

  array.swap!(less_array_pointer, right_index)

  return less_array_pointer

class Array
  def swap!(a,b)
    self[a], self[b] = self[b], self[a]
  • \$\begingroup\$ +1. Just some comments: 1) I'd use each instead of for (more idiomatic). 2) Some spaces seem to be missing (for example on middle_index=(... \$\endgroup\$
    – tokland
    Mar 7, 2014 at 8:03

Integer Overflow

I'm not very confident with ruby but I'm assuming this is integer arithmetic (otherwise you could have a floating point index, which doesn't make sense):


If it indeed is integer arithmetic you will have an integer overflow if you're dealing with large arrays.

You should implement it as:

 m = l + (r - l)/2; 

which will not overflow for any 0 <= l <= r.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.