260. Which sorting algorithm is best for a singly linked list, and why?
MediumSorting
Technical
Show model answer
Merge sort. Splitting is done with slow and fast pointers, and merging two sorted lists only relinks nodes, so no auxiliary array is needed. It runs in O(n log n) time; the recursive version uses O(log n) stack and the bottom-up version (merge runs of length 1, 2, 4, …) uses O(1) extra space. It is also stable.
Quicksort is a poor fit because it relies on random access and in-place swapping, and its pivot choices are harder to randomize on a list. Heap sort needs random access to the heap array. Insertion sort works naturally on lists but is O(n²).