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 earlier 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)

Ruby uses some kind of Quicksort to sort its arrays. Unfortunately Quicksort is not stable.
When you get sorted data from your database, which almost certainly sorts faster than anything in Ruby, you sometimes may want the data to be resorted in a stable way.

I found following snippet:

class Array
  def stable_sort
    n = 0
    sort_by {|x| n+= 1; [x, n]}
  end
end

I extended it to accept a block like the original sort method does:

class Array
  def stable_sort
    n = 0
    c = lambda { |x| n+= 1; [x, n]}
    if block_given?
      sort { |a, b|
        yield(c.call(a), c.call(b))        
      }
    else
      sort_by &c
    end
  end
end

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.