Swift: Merge Sort Algorithmus mit alternativen Schlüsseln

Question

Ich habe ein Objekt mit Eigenschaften: Name, Relevanz, Timestamp.

Ich möchte, dass die Objekte im Array interlaced nach relevantesten ("Relevanz") und neuesten ("Timestamp") sortiert werden.

Wie zum Beispiel: Relevant, Neu, Relevant, Neu, etc ...

Jetzt habe ich eine Lösung auf der Basis einer einzigen Taste mit Zeitkomplexität von O (n log n) zu sortieren.

Hier ist meine Lösung in Swift:

func mergeSort(array: [Entity]) -> [Entity] { 
    guard array.count > 1 else { return array } // 1 

    let middleIndex = array.count/2    // 2 

    let leftArray = mergeSort(Array(array[0..<middleIndex]))    // 3 

    let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4 

    return merge(leftPile: leftArray, rightPile: rightArray)    // 5 
} 


    func merge(leftPile leftPile: [Entity], rightPile: [Entity]) -> [Entity] { 
    // 1 
    var leftIndex = 0 
    var rightIndex = 0 

    // 2 
    var orderedPile = [Entity]() 

    // 3 
    while leftIndex < leftPile.count && rightIndex < rightPile.count { 
      if leftPile[leftIndex].timestamp.isGreaterThanDate(rightPile[rightIndex].timestamp) { 
       orderedPile.append(leftPile[leftIndex]) 
       leftIndex += 1 
      } else if leftPile[leftIndex].timestamp.isLessThanDate(rightPile[rightIndex].timestamp) { 
       orderedPile.append(rightPile[rightIndex]) 
       rightIndex += 1 
      } 
      else{ 
       orderedPile.append(leftPile[leftIndex]) 
       leftIndex += 1 
       orderedPile.append(rightPile[rightIndex]) 
       rightIndex += 1 
      } 
    } 

    // 4 
    while leftIndex < leftPile.count { 
     orderedPile.append(leftPile[leftIndex]) 
     leftIndex += 1 
    } 

    while rightIndex < rightPile.count { 
     orderedPile.append(rightPile[rightIndex]) 
     rightIndex += 1 
    } 

    return orderedPile 
} 

Der Code sortiert die Array für „Neueste“ perfekt und ich kann auch den Schlüssel von „Zeitstempel“ auf „Relevanz“ ändern, es zu sortieren für „Most Relevant".

Aber ich möchte interlaced sortieren wie oben beschrieben mit der kürzesten Komplexität. Hat jemand eine gute Lösung dafür?

Answer 1

Nach Relevanz sortieren.

Erstellen Sie eine Kopie nach Aktualität sortiert.

Die Kopien in alternativer Reihenfolge zusammenführen, ein Wörterbuch der Zusammenführung beibehalten und nicht erneut hinzufügen.

Die zwei Sortierungen sind O(n log(n)) und die Zusammenführung ist O(n) für O(n log(n)).