Stooge Sort in Ruby

Overview

Stooge Sort is another inefficient sorting algorithm which has a time complexity of O(n^(log 3 / log 1.5)).

Concise

def stooge_sort(a, s, f)
  if a[s] > a[f]
    a[s], a[f] = a[f], a[s]
  end
  p a

  if (f-s+1) > 2
    t = (f-s+1) / 3

    stooge_sort(a, s, f-t)
    stooge_sort(a, s+t, f)
    stooge_sort(a, s, f-t)
  end

  a
end

u = (0..9).to_a.sort{ rand() - 0.5 }[0..7]
p u

s = stooge_sort(u, 0, u.length-1)
p s
stooge_sort.rb

Verbose

# Stooge Sort
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def stooge_sort(numbers, start, finish)

  # If the first element is larger than the last, swap them.
  if numbers[start] > numbers[finish]
    numbers[start], numbers[finish] = numbers[finish], numbers[start]
  end

  p numbers

  # If there are more than 2 elements, recursively Stooge Sort the
  # first two thirds, then the last two thirds, then the first two thirds again.
  if (finish - start + 1) > 2
    third = (finish - start + 1) / 3

    stooge_sort(numbers, start, finish - third)
    stooge_sort(numbers, start + third, finish)
    stooge_sort(numbers, start, finish - third)
  end

  numbers
end

# Generate array of ten random integers.
unsorted = (0..9).to_a.sort{ rand() - 0.5 }[0..7]
puts unsorted.inspect

# Sort.
sorted = stooge_sort(unsorted, 0, unsorted.length-1)
puts sorted.inspect
stooge_sort_verbose.rb

Sample Input and Output

$ ruby stooge_sort.rb
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 9, 8, 2, 7, 0, 5]
[1, 6, 8, 9, 2, 7, 0, 5]
[1, 6, 8, 9, 2, 7, 0, 5]
[1, 6, 8, 9, 2, 7, 0, 5]
[1, 6, 8, 9, 2, 7, 0, 5]
[1, 6, 8, 9, 2, 7, 0, 5]
[1, 6, 8, 9, 2, 7, 0, 5]
[1, 6, 7, 9, 2, 8, 0, 5]
[1, 6, 2, 9, 7, 8, 0, 5]
[1, 6, 2, 9, 7, 8, 0, 5]
[1, 6, 2, 7, 9, 8, 0, 5]
[1, 6, 2, 7, 9, 8, 0, 5]
[1, 6, 2, 7, 9, 8, 0, 5]
[1, 6, 2, 7, 9, 8, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 6, 2, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 6, 7, 8, 9, 0, 5]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 8, 9, 0, 6]
[1, 2, 5, 7, 6, 9, 0, 8]
[1, 2, 5, 7, 0, 9, 6, 8]
[1, 2, 5, 7, 0, 9, 6, 8]
[1, 2, 5, 7, 0, 6, 9, 8]
[1, 2, 5, 7, 0, 6, 9, 8]
[1, 2, 5, 7, 0, 6, 9, 8]
[1, 2, 5, 7, 0, 6, 9, 8]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 5, 7, 0, 6, 8, 9]
[1, 2, 0, 7, 5, 6, 8, 9]
[1, 2, 0, 7, 5, 6, 8, 9]
[1, 2, 0, 5, 7, 6, 8, 9]
[1, 2, 0, 5, 7, 6, 8, 9]
[1, 2, 0, 5, 7, 6, 8, 9]
[1, 2, 0, 5, 7, 6, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[1, 2, 0, 5, 6, 7, 8, 9]
[0, 2, 1, 5, 6, 7, 8, 9]
[0, 2, 1, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]
[0, 1, 2, 5, 6, 7, 8, 9]

Further Reading