Top Level Namespace

Defined Under Namespace

Modules: MIDI

Instance Method Summary collapse

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