From: Yong Li <gilbertly@...>
Date: 2012-01-19T15:05:50+09:00
Subject: Re: Elegant expression of sorting

On Thu, Jan 19, 2012 at 8:58 AM, Garthy D
<garthy_lmkltybr@entropicsoftware.com> wrote:
> Hi all,
>
> I've found that for the current project I am working on that I am frequently
> doing sorts based on multiple keys. The comparisons on each key tend to
> vary, ie. sometimes I want descending rather than ascending, and other times
> the comparison itself is complex.
>
> I usually do something like this:
>
> foo.sort! {|a,b|
>  # Ascending, primary.
>  rv = a.key0 <=> b.key0
>  # Descending, secondary.
>  rv = b.key1 <=> a.key1 if rv == 0
>  # A tricky and expensive comparison, tertiary.
>  rv = a.magic(b) if rv == 0
>  rv
> }
>
> Does anyone have any suggestions as to a more elegant way to express this?
> I'm after something that is logically equivalent, but easier to write and
> clearer to read.
>
> Garth
>

A general way to perform a multi-key sort is:
# assuming sort() is a stable sort algorithm, e.g. merge sort
  foo.sort! {|a,b|
     # starting from the least important key
     a.magic(b)
  }
  foo.sort! {|a,b|
     # sort again using the second-least important key
     b.key1 <=> a.key1
  }
  # repeat until you are done with the most important key

I guess you can generalize this using an array of Lambdas.

One potential disadvantage of this for your particular case is that,
a.magic(b) is always performed even if a.key0 != b.key0. As you have
stated, this is quite expensive, and can make the above general scheme
much more expensive than your way.