¿Cuál es la forma inteligente de implementar OrderBy/ThenBy?

Question

Estoy implementando un clon LINQ en Lua, pero eso no es demasiado relevante aquí, y tengo la mayoría de las funciones hechas (enumerable/consultable, no el precompilador todavía), pero no puedo pensar en una forma inteligente de implementar OrderBy's Entonces por.

Actualmente ordeno una vez, luego coloco en nuevas listas y luego ordeno esas listas secundarias y finalmente fusiono los resultados nuevamente, pero eso parece muy derrochador y poco elegante, estoy seguro de que alguien ha descubierto una forma inteligente de hacerlo (mejor algoritmo), pero no tengo idea de qué se trata. ¿Alguna pista sobre cómo implementar OrderBy/Thenby de una manera eficiente?

Nota: construcciones de lenguaje y lenguaje con suerte no son relevantes aquí, estoy buscando el algoritmo generalizado, al igual que decir que una clasificación binaria se puede hacer en cualquier idioma.

Edit: Actualmente estoy trabajando en LINQ to Object, por lo que cualquier idea de cómo se haría en particular sería genial. Supongo que OrberBy/ThenBy son 2 llamadas a funciones, no una, pero podría estar equivocado.

Answer 1

Normalmente, implementaría una ordenación multi-clave utilizando un método de comparación adecuado. Por ejemplo, para ordenar una lista de nombres por apellido y luego el nombre, es posible utilizar una función de comparación de esta manera:

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

El punto clave aquí es que no nos fijamos en el miembro menos que FirstName Ya sé que los dos miembros LastName son iguales.

Answer 2

Creo que esto también funciona:

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

el cual, de ser cierto, significa que esto debería funcionar:

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