Qual è il modo intelligente di implementare OrderBy/ThenBy?

Question

Sto implementando un clone LINQ in Lua, ma non è troppo rilevante qui, e ho fatto la maggior parte delle funzioni fatte (enumerabile/interrogabile, non ancora il precompilatore), ma non riesco a pensare a un modo intelligente per implementare OrderBy ThenBy.

Attualmente mi sorta una volta, quindi collocare in nuove liste e quindi ordinare tali elenchi secondari ed infine unire nuovamente i risultati, ma che sembra molto dispendioso e poco elegante, sono sicuro che qualcuno ha trovato un modo intelligente per fare questo (algoritmo migliore), ma non ho idea di cosa sia. Eventuali indizi su come implementare OrderBy/Thenby in modo efficiente?

Nota: I costrutti linguistici e linguistici si spera non siano rilevanti qui, sto cercando l'algoritmo generalizzato, così come dire che un ordinamento binario può essere fatto in qualsiasi lingua.

Modifica: Attualmente sto lavorando a LINQ su Oggetto, quindi qualsiasi idea su come sarebbe stata eseguita in particolare sarebbe ottima. Sto indovinando OrberBy/ThenBy sono 2 chiamate di funzione, non una, ma potrei sbagliarmi.

Answer 1

In genere si implementa un ordinamento a più chiavi utilizzando un metodo di confronto adatto. Ad esempio, per ordinare un elenco di nomi per il cognome e poi il nome, si potrebbe utilizzare una funzione di confronto come questo:

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

Il punto chiave qui è che noi non guardiamo il FirstName membro a meno che non già sappiamo che i due membri LastName sono uguali.

Answer 2

Credo che questo funziona anche:

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

che, se è vero, significa che questo dovrebbe funzionare:

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