Какой разумный способ реализовать OrderBy / ThenBy?

Question

Я внедряю клон LINQ в Lua, но здесь это не слишком актуально, и я выполнил большинство функций (перечислимых / запрашиваемых, но не прекомпилятор), но не могу придумать разумного способа реализации OrderBy's ThenBy.

В настоящее время я сортирую один раз, затем помещаю в новые списки, а затем сортирую эти подсписки и, наконец, снова объединяю результаты, но это кажется очень расточительным и не элегантным, я уверен, что кто-то нашел разумный способ сделать это (лучше алгоритм), но я понятия не имею, что это такое. Любые подсказки относительно того, как эффективно реализовать OrderBy / Thenby?

Примечание: Надеемся, что язык и языковые конструкции здесь не актуальны, я ищу обобщенный алгоритм, точно так же как, скажем, двоичная сортировка может быть сделана на любом языке.

Редактировать: В настоящее время я работаю над LINQ to Object, поэтому любые идеи о том, как это будет сделано, в частности, будут великолепны. Я предполагаю, что OrberBy / ThenBy - это 2 вызова функций, а не один, но я могу ошибаться.

Answer 1

Как правило, вы реализуете многоключевую сортировку, используя подходящий метод сравнения. Например, чтобы отсортировать список имен по фамилии, а затем по имени, вы можете использовать функцию сравнения, например:

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;
    }
}

Ключевым моментом здесь является то, что мы не смотрим на член FirstName, если не знаем, что два члена LastName равны.

Answer 2

Я думаю, это также работает:

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

, что, если верно, означает, что это должно работать:

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