## 7.7 Comparison of Mergesort, Quicksort, and Heapsort [Table 7.2](#ch07table02)summarizes our results concerning the three algorithms. Because Heapsort is, on the average, worse than Quicksort in terms of both comparisons of keys and assignments of records, and because Quicksort's extra space usage is minimal, Quicksort is usually preferred to Heapsort. Because our original implementation of Mergesort ([Algorithms 2.2](LiB0016.html#158)and [2.4](LiB0016.html#169))uses an entire additional array of records, and because Mergesort always does about three times as many assignments of records as Quicksort does on the average, Quicksort is usually preferred to Mergesort even though Quicksort does slightly more comparisons of keys on the average. However, the linked implementation of Mergesort ([Algorithm 7.4](LiB0055.html#661)) eliminates almost all the disadvantages of Mergesort. The only disadvantage remaining is the additional space used for Θ (*n*) extra links. ****Table 7.2: Analysis summary for Θ (*n* lg *n*) sorting algorithms\[[\*](#ftn.ch07table02fnt01)\]Algorithm Comparisons of Keys Assignments of Records Extra Space Usage Mergesort *W* (n) = n *lg* n T (*n*) = 2*n* lg *n* Θ (*n*) records ([Algorithm 2.4](LiB0016.html#169)) *A (n) = n* lg *n* Mergesort *W* (n) = *n*lg*n* T (*n*) = 0\[[†](#ftn.ch07table02fnt02)\] Θ (*n*) links ([Algorithm 7.4](LiB0055.html#661)) *A* (n) = *n*lg*n* Quicksort *W (n) = n*2/2 Θ (lg *n*) indices (with improvements) A (*n*) = 1.38*n* lg *n* A (*n*) = 0.69*n* lg *n* Heapsort *W (n*) = 2*n* lg *n* W (n) = *n* lg *n* In-place A (*n*) = 2*n* lg *n* A (n) = *n* lg *n* \[[\*](#ch07table02fnt01)\]Entries are approximate; the average cases for Mergesort and Heapsort are slightly better than the worst cases. tIf it is required that the records be in sorted sequence in contiguous array slots, the worst case is in Θ (*n*). \[[†](#ch07table02fnt02)\]If it is required that the records be in sorted sequence in contiguous array slots, the worst case is in Θ (*n*). ****