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