Question

The runtime of Kruskal’s algorithm is dominated by the cost of this task used to process the edges. In the original conceptualization of one algorithm for this task, two pointers iteratively converge until an inversion is found. The most efficient implementation of that algorithm for this task on an unknown (10[1])input involves choosing a pivot element (10[1])at random. (10[2])The last step in a popular algorithm for this task is a k-way subroutine which outputs an ordered list. An “insertion” (10[1])algorithm for this task is typically used when the number of elements is below a threshold value. (10[1])For 10 points, name this task which is guaranteed to be computed stably by a “merge” algorithm, but not a “quick” algorithm. ■END■

ANSWER: sorting [accept insertion sort or mergesort or quicksort]
<Science - Other Science>
= Average correct buzz position

Back to tossups

Buzzes

PlayerTeamOpponentBuzz PositionValue
Edward Zhou (DII)NYU ALehigh4910
Alex Shi (DII)Swarthmore BColumbia B5510
Geoffrey Wu (UG)Columbia AFordham5710
Ashish KumbhardareRowanNYU B5710
Rio Lucenet (UG)NYU CUniversity of Delaware A7810
Kaiden Carey (DII)PennSwarthmore A9510

Summary

2023 ACF Fall (Rutgers)10/14/2023Y6100%0%0%65.17