class Object

Public Instance Methods

mergesort(arr, &cmp) click to toggle source

A stable sorting algorithm that maintains the relative order of equal elements.

This code used to be in a new subclass of Array, but that started causing problems in Ruby 3.0, apparently due to the return type of the ‘[]` operator which was the parent Array class.

This code borrowed from ‘Moser’ codesnippets.joyent.com/posts/show/1699

# File lib/midilib/mergesort.rb, line 14
def mergesort(arr, &cmp)
  cmp = ->(a, b) { a <=> b } if cmp.nil?
  if arr.size <= 1
    arr.dup
  else
    halves = mergesort_split(arr).map { |half| mergesort(half, &cmp) }
    mergesort_merge(*halves, &cmp)
  end
end
mergesort_merge(first, second, &predicate) click to toggle source
# File lib/midilib/mergesort.rb, line 29
def mergesort_merge(first, second, &predicate)
  result = []
  until first.empty? || second.empty?
    result << if predicate.call(first.first, second.first) <= 0
                first.shift
              else
                second.shift
              end
  end
  result.concat(first).concat(second)
end
mergesort_split(arr) click to toggle source
# File lib/midilib/mergesort.rb, line 24
def mergesort_split(arr)
  n = (arr.length / 2).floor - 1
  [arr[0..n], arr[n + 1..-1]]
end