Top Level Namespace
Defined Under Namespace
Modules: MIDI
Instance Method Summary collapse
-
#mergesort(arr, &cmp) ⇒ Object
A stable sorting algorithm that maintains the relative order of equal elements.
- #mergesort_merge(first, second, &predicate) ⇒ Object
- #mergesort_split(arr) ⇒ Object
Instance Method Details
#mergesort(arr, &cmp) ⇒ Object
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
14 15 16 17 18 19 20 21 22 |
# 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) ⇒ Object
29 30 31 32 33 34 35 36 37 38 39 |
# 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) ⇒ Object
24 25 26 27 |
# 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 |