Sortieralgorithmus für dieses spezifische Szenario verwenden

Question

Ich habe zwei Listen - nennen wir sie Details und Summen.

Die Elemente in Details haben für jede Taste mehrere Elemente, die die Liste sortiert wird, wie zum Beispiel:

KEY1
KEY1
TASTE2
TASTE2
KEY3
KEY3
KEY3
usw.

Die Artikel in beträgt wird nur jede Taste einmal haben, wie zum Beispiel:

KEY1
TASTE2
KEY3
etc

Beide Listen von Schlüssel bereits sortiert sind. Die Listen müssen kombiniert werden, so dass die neue Liste der Details hat Elemente gefolgt von seinem entsprechenden Element aus Summen, als solche:

KEY1 (dies ist aus Details)
KEY1 (dies ist aus Details)
KEY1 (dies ist aus Summen) etc

Welche Algorithmus Sortierung in der besten Leistung in diesem Szenario führen wird?

(ganz ehrlich, ich werde einfach den Code ändern, so dass die Reihe von beträgt erstellt-und-eingefügt wie die Details Liste gebaut wird, ist dies eher eine akademische Frage)

Answer 1

Wenn Sie die beiden Listen zu einem zusammenfassen und sie bereits sortiert sind, sollten Sie nicht zurück greifen.

Eine einfache Zusammenführung wird tun, wie folgt. Dies setzt voraus, dass Ihre Annahmen korrekt sind und es keine "nackten" Details oder Gesamtlinien gibt (Details ohne Gesamtsummen oder Gesamtsummen ohne Details). Wenn dies der Fall ist, benötigen Sie zusätzlichen Code, aber das Prinzip ist das gleiche.

Get first detail-list 
Get first total-list 

While total-list not finished: 
    If detail-list.key > total-list.key: 
     Output total-list 
     Get next total-list 
     Next while 
    Output detail-list 
    Get next detail-list