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

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.