Tag: sort

Mergesort in Ruby

Posted by Moser on September 18, 2008

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)

Advanced Array Sorting in Ruby

Posted by Moser on September 16, 2008

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