日々の流転

λ. ホンカン

ホンカン発見。

λ. マージソート

安定なソートの話がどっかであったので、現実逃避に書いたマージソート。ださーい。それに、Range#begin=とRange#end=欲しいなぁ。そーいや、Range#lengthってIntegerの場合はsucc使わないのね…

class Array
  def msort!(&compare)
    tmp = Array.new(self.length)

    compare = lambda{|i,j| i<=>j} if compare.nil?

    sort = lambda{|a|
      if a.length > 1
	l = a.begin...(a.begin + a.length / 2)
	r = l.end...a.end

	sort.call(l)
	sort.call(r)

	i = a.begin
	while l.length > 0 and r.length > 0
	  if compare.call(self[l.begin], self[r.begin]) <= 0
	    tmp[i] = self[l.begin]
	    l = l.begin.succ...l.end
	  else
	    tmp[i] = self[r.begin]
	    r = r.begin.succ...r.end
	  end
	  i = i.succ
	end

	tmp[i, l.length] = self[l] if l.length > 0
	self[a.begin...r.begin] = tmp[a.begin...r.begin]
      end
    }

    sort.call(0...length)
    self
  end
end