# Is it possible to sort a linked list without copying its values but linking the nodes?

Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order.

Also can this be done in a quadratic time?

I will be attempting this in Python.

• Welcome to ComputerScience@SE. Can you pinpoint any additional difficulty introduced by no copying? When you add whether this is about singly linked list or doubly linked ones, please correct the typo in the title. – greybeard Nov 24 '19 at 22:31
• – D.W. Nov 25 '19 at 4:05

Copy the list into an array, sort the array, construct a linked list from it. Done. It suffices to populate the array with pointers (references) to the values; you don't need to copy the values themselves. The running time will be $$\Theta(n \log n)$$ if you use an appropriate sorting algorithm -- much faster than quadratic time.

• Without copying its value means that u cant even copy to an array – Turing101 Nov 25 '19 at 3:45
• You only copy pointers, not values. Funny enough, I had that as an interview question once. Even for sorting arrays it would be useful if copying values is much more expensive than comparing, because it lets you get away with O(n) copy operations. – gnasher729 Nov 25 '19 at 8:54

Quicksort and mergesort can both be implemented to work directly on a linked list with just $$O(1)$$ extra space. This actually improves the space complexity of the usual mergesort, which ordinarily requires $$O(n)$$ working space (this is because the pointers actually constitute $$O(n)$$ extra space themselves). As usual, mergesort will take $$O(n\log n)$$ time in the worst case, while quicksort has an $$O(n^2)$$ worst-case time but is $$O(n\log n)$$ on "most" inputs.

For quicksort, on each subproblem you can walk the list to find a suitable pivot without hurting the asymptotic complexity. Each partition step consists of simply growing 2 lists, those < the pivot and those >= it. Then append the pivot to the end of the first list, and the second list to that.

For mergesort, to find the halfway point of a singly linked list, walk 2 pointers forward, with one (the "hare") advancing twice at each step and the other (the "tortoise") only once. Once the hare reaches the end, the tortoise is halfway. Now you can merge the two half-length sublists that begin at the start of the original list, and at the tortoise.

Insertion sort can also be straightforwardly implemented to run directly on a linked list, but this is probably a bad choice as its performance will be $$O(n^2)$$ unless the list is already nearly reverse-sorted (note the difference to the array version in which insertion sort is fast on nearly sorted inputs). This is because the intermediate solution gets built by taking the next element and appending it to the front of the result, meaning it gets built in reverse order.

If you really, really want no extra space, you can do bubble sort. Normally bubble sort works on an array, starts at the first item, proceeds to the last item and exchanges consecutive items. You can do all this with a linked list.