Quicksort, mergesort, etc.

sorts.rb

require 'benchmark'

def quick_sort(array)
  return array if array.size <= 1

  pivot ||= array.shift

  left = array.select { |n| n < pivot }
  right = array.select { |n| n >= pivot }

  return [*quick_sort(left), pivot, *quick_sort(right)]
end

def merge_sort(array)
  return array if array.size <= 1

  left, right = array.each_slice((array.size/2.0).round).to_a

  merge = -> (left, right) {
    array = []
    while left.size > 0 && right.size > 0
      array << (left[0] < right[0] ? left.shift : right.shift)
    end

    return array + left + right
  }

  return merge.call merge_sort(left), merge_sort(right)
end

array = (1..100).to_a.shuffle

sorted_array = array.sort
merge_sorted_array = merge_sort(array)
quick_sorted_array = quick_sort(array)

puts (sorted_array == quick_sorted_array ? "QS: Pass": "QS: Fail")
puts (sorted_array == merge_sorted_array ? "MS: Pass": "MS: Fail ")

puts "Quick sort   : #{quick_sort(array) * ", "}"
puts "Default sort: #{array.sort * ", "}"
puts "Merge sort   : #{merge_sort(array) * ", "}"

puts "Quick sort   : #{puts Benchmark.measure { quick_sort(array) } }"
puts "Default sort: #{puts Benchmark.measure { array.sort } }"
puts "Merge sort: #{puts Benchmark.measure { merge_sort(array) } }"