merge two sorted arrays

gistfile1.rb

#!/usr/bin/env ruby
require 'time'
require 'benchmark'

class Thing
  attr_accessor :timestamp
  def initialize(timestamp)
    @timestamp = timestamp
  end

  def self.next_time(i)
    time = Time.now - (i * 60)
    time.iso8601(3)
  end
end


def generate_things(count = 100)
  things = []
  1.upto(count) do |i|
    things << Thing.new(Thing.next_time(i))
  end
  things
end

def merge(l, r)
  l, r = l.dup, r.dup
  x = []
  while x.length < 25 and l.length > 0 and r.length > 0
    if l.at(0).timestamp >= r.at(0).timestamp
      x.push l.shift
    else
      x.push r.shift
    end
  end
  return x if x.length >= 25

  if l.length > 0
    x.concat l
  else
    x.concat r
  end
  x
end

def nocopy_merge(l, r)
  lcount, rcount = l.size, r.size
  lin, rin = 0, 0
  x = []
  while lin+rin < 25 and lin < lcount and rin < rcount
    if l.at(lin).timestamp >= r.at(rin).timestamp
      x.push l.at(lin)
      lin += 1
    else
      x.push r.at(rin)
      rin += 1
    end
  end
  return x if lin+rin == 25

  if lin < lcount
    x.concat l[lin, lcount]
  else
    x.concat r[rin, rcount]
  end
  x
end

one = generate_things
two = generate_things

Benchmark.bmbm(10) do |x|
  x.report("merge:") { 50_000.times { merge(one, two) } }
  x.report("nocopy:") { 50_000.times { nocopy_merge(one, two) } }
end