What's the smart way to implement OrderBy / ThenBy?

Question

I'm implementing a LINQ clone in Lua, but that's not too relevant here, and I've got most features done (enumerable/queryable, not the precompiler yet), but can't think of a smart way to implement OrderBy's ThenBy.

Currently I sort once, then place in new lists and then sort those sub lists and finally merge the results again, but that seems very wasteful and inelegant, I'm sure someone has figured out a smart way to do this (better algorithm), but I have no idea what it is. Any clues as to how to implement OrderBy / Thenby in an efficient way?

Note: Language and Language constructs hopefully are not relevant here, I'm looking for the generalized algorithm, just as say a Binary Sort can be done in any language.

Edit: Currently I'm working on LINQ to Object, so any ideas how that would be done in particular would be great. I'm guessing OrberBy/ThenBy are 2 function calls, not one but I might be wrong.

Answer 1

Typically you would implement a multi-key sort by using a suitable compare method. For example, to sort a list of names by last name and then first name, you might use a compare function like this:

int compareNames(Name n1, Name n2)
{
    if (n1.LastName < n2.LastName) {
        return -1;
    } else if (n1.LastName > n2.LastName) {
        return 1;
    } else if (n1.FirstName < n2.FirstName) {
        return -1;
    } else if (n1.FirstName > n2.FirstName) {
        return 1;
    } else {
        return 0;
    }
}

The key point here is that we don't look at the FirstName member unless we already know that the two LastName members are equal.

Answer 2

I think this also works:

function(lh,rh)
    if lh.first < rh.first then
     return true
    elseif lh.second < rh.second then
     return true
    end
    return false
end

which, if true, means this should work:

tests={}
tests[1]=function(lh,rh) 
    return lh.first < rh.first
end
tests[2]=function(lh,rh)
    return lh.second < rh.second
end

function(lh,rh)
    local res=true
    local k,v
    for k,v in ipairs(tests) do
     res = v(lh,rh)
     if res then break end
    end
    return res
end