Merge Sort. (Check geeksforgeeks for the the algorithm) Quicksort is definitely not the answer because it takes up a lot of space and is also very complex when we need to keep iterating from two opposite ends of a linklist.