Ich habe mich mit dem Thema der Zusammenführung befasst, bei dem ich auf das Konzept gestoßen bin, dass die Anzahl der Vergleiche bei der Zusammenführung (im schlimmsten Fall und entsprechend)Wikipedia) ist gleich (n ⌈ lg n⌉ - 2⌈Lg n⌉ + 1); in der Tat liegt es zwischen (n lg n - n + 1) und (n lg n + n + O (lg n)). Das Problem ist, dass ich nicht herausfinden kann, was diese Komplexität zu sagen versucht. Ich weiß, O (nlogn) ist die Komplexität der Zusammenführungssortierung, aber die Anzahl der Vergleiche?