Which of the following sorting algorithms can be used to sort a random linked…

Concept: A sorting algorithm is efficient on a linked list only if (a) every step it needs can be done through sequential traversal rather than O(1) random access to an arbitrary index, and (b) it still keeps a good worst-case time complexity. An array-based heap sort genuinely needs direct index access between a node and its parent/children, which a linked list cannot provide efficiently, so it is ruled out on access grounds alone. Quick sort, by contrast, CAN be adapted to a linked list through purely sequential partitioning (walking the list and relinking nodes above/below a chosen pivot) — but doing so does not change its complexity floor.

Application: heap sort's parent/child index arithmetic (i to 2i+1, 2i+2) cannot be done efficiently without an array's O(1) indexing, so it is infeasible here regardless of complexity. Quick sort's worst-case running time is still O(n2) on a poor pivot choice, exactly as on an array, so adapting it to sequential access does not give it the minimum guaranteed complexity. That leaves insertion sort and merge sort as the two algorithms that both run purely on sequential access AND have a fixed, pivot-independent worst case. Merge sort finds the midpoint of the list using the slow/fast pointer technique, recursively sorts each half, and merges two already-sorted halves by walking both from the front and relinking nodes — all through sequential traversal.

Cross-check: comparing worst-case running time directly, insertion sort is O(n2) and quick sort is also O(n2) in the worst case, while merge sort is O(n log n). Since n log n grows strictly slower than n2 for large n, merge sort has the lowest guaranteed asymptotic complexity among the algorithms that work efficiently on a linked list.

So the algorithm that sorts a random linked list with the minimum time complexity is merge sort.