Swift: Merge Sort Algorithm с альтернативными ключами

Question

У меня есть объект со свойствами: Name, Relevance, Timestamp.

Я хочу, чтобы объекты в массиве были отсортированы с чередованием по большинству релевантных («Релевантность») и «Самые последние» («Временная метка»).

Такие, как: уместность, Последние, актуальные, новое, и т.д. ...

Теперь, у меня есть решение для сортировки на основе одного ключа с временной сложности O (N журнал N).

Вот мое решение в 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 
} 

код сортирует массив для «Самые последние» отлично и я также может изменить ключ от «метки времени» до «значимости», сортировать его «Самые Соответствующий".

Но, я хочу, чтобы чересстрочная сортировка, как описано выше, с наименьшей сложностью. У кого-нибудь есть хорошее решение для этого?

Answer 1

Сортировка по релевантности.

Составьте копию отсортированную по количеству раз.

Объедините копии в альтернативном порядке, сохранив словарь из них в слиянии и не добавляя их снова.

Два вида: O(n log(n)), а слияние O(n) для O(n log(n)).