Moserei

While playing around with stable sorting I implemented Mergesort.

class Array
  def mergesort(&cmp)
    if cmp == nil
      cmp = lambda { |a, b| a <=> b }
    end
    if size <= 1
      self.dup
    else
       halves = split.map{ |half|
        half.mergesort(&cmp)
      }
      merge(*halves, &cmp)
    end
  end

 
  protected
  def split
    n = (length / 2).floor - 1
    [self[0..n], self[n+1..-1]]
  end

  def merge(first, second, &predicate)
    result = []
    until first.empty? || second.empty?
     if predicate.call(first.first, second.first) <= 0
        result << first.shift
      else
        result << second.shift
      end 
    end
    result.concat(first).concat(second)
  end
end

It is not suitable for productive use as it’s quite slow. It’s about ten times slower than the stable_sort method from my another post. A little benchmark sorting an array of 2,000,000 random integers:

                user     system      total        real
Original Sort 0.630000   0.010000   0.640000 (  0.639860)
Stable Sort  12.780000   0.700000  13.480000 ( 13.477982)
Mergesort   109.170000  13.420000 122.590000 (122.617323)

While developing a member management application for my soaring club I found out quite a little about sorting arrays in Ruby. Rubys sort uses the operator <=>:

irb(main):001:0> 1 <=> 2
=> -1
irb(main):002:0> 1 <=> 0
=> 1
irb(main):003:0> 1 <=> 1
=> 0

By implementing it on your class you can specify a way in which an array of instances should be sorted. Here is a fragment of my Member class:

def <=>(b)
  name <=> b.name
end

My members will be sorted by their name. But sometimes you need a special sorting. Thats why the sort method accepts a block to specify a way of sorting

arr.sort! do |a, b|
  a.birthdate.yday <=> b.birthdate.yday
end

This is the sorting I needed for a list of birthdays. Sure enough you can do anything inside the block as long as it returns -1, 0 or 1. It’s no problem to sort by 2 attributes:

arr.sort! do |a, b|
  r = a.birthdate.yday <=> b.birtdate.yday
  r = a.name <=> b.name if r == 0
  r
end

The rainy weather should actually encourage me to study analysis, but it rather made me go through old email. I found one reminding me of this domain I registered some time ago, which I never really used. So I thought I could finally join the community of bloggers and kill some time by installing Wordpress and playing around.