# Why don't we use quick sort on a linked list?

Quick sort algorithm can be divided into following steps

1. Identify pivot.

2. Partition the linked list based on pivot.

3. Divide the linked list recursively into 2 parts.

Now, if I always choose last element as pivot, then identifying the pivot element (1st step) takes $\mathcal O(n)$ time.

After identifying the pivot element, we can store its data and compare it with all other elements to identify the correct partition point (2nd step). Each comparison will take $\mathcal O(1)$ time as we store the pivot data and each swap takes $\mathcal O(1)$ time. So in total it takes $\mathcal O(n)$ time for $n$ elements.

So the recurrence relation is:

$T(n) = 2T(n/2) + n$ which is $\mathcal O(n \log n)$ which is the same as in merge sort with a linked list.

So why is merge sort preferred over quick sort for linked lists?

• There is no need to pick the last element as the pivot instead of the first Nov 13, 2018 at 21:35

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result.
At the same time the merge sort is external, it requires additional array to return ordered result. In array it means additional space overhead, in the case if linked list, it is possible to pull value out and start merging nodes. The access is more sequential in nature.

Because of this, the quicksort is not natural choice for linked list while merge sort takes great advantage.

The Landau notation might (more or less, because Quicksort is still $\mathcal O(n^2)$) agree, but the constant is far higher.

In the average case both algorithms are in $\mathcal O(n\log n)$ so the asymptotic case is the same, but preference is strictly due to hidden constant and sometimes the stability is the issue (quicksort is inherently unstable, mergsort is stable).

• But the average time complexity is same right ? Using quick sort as well as merge sort for linked list . Nov 30, 2017 at 21:07
• @Zephyr, you need to remember that complexity notation drops constant factors. Yes, quicksort on a linked list and mergesort on a linked list are the same complexity class, but those constants you're not seeing make mergesort uniformly faster.
– Mark
Nov 30, 2017 at 23:59
• @Zephyr Basically it's the difference of theoretical and empirical results. Empirically, quicksort is quicker. Dec 1, 2017 at 5:31
• Also, selecting a good pivot is difficult for a linked list. If you take the last element, like OP suggests, that means that the worst case ($O(n^2)$) is an already sorted list or sublist. And that worst case is quite likely to appear in practice. Dec 1, 2017 at 8:39
• Quicksort is never in place, that’s a common misconception. It requires $\mathcal{O}(\operatorname{log} n)$ additional space. Furthermore, the “random” memory access pattern is also not quite accurate: it depends crucially on the choice of pivot, as explained in the other answer. Dec 1, 2017 at 13:31

You can quick sort linked lists however you will be very limited in terms of pivot selection, restricting you to pivots near the front of the list which is bad for nearly sorted inputs, unless you want to loop over each segment twice (once for pivot and once for partition). And you will need to keep a stack of the partition boundaries for the lists you still need to sort. That stack can grow to $O(n)$ when pivot selection is bad along with the time complexity growing to $O(n^2)$.

Merge sort on linked lists can be executed using only $O(1)$ extra space if you take a bottom-up approach by counting where the boundaries of the partitions are and merging accordingly.

However adding a single 64 element array of pointers you can avoid that extra iteration and sort lists of up to $2^{64}$ elements in $O(1)$ additional extra space.

head = list.head;
head_array = array of 64 nulls

current.next = null;
for(i from 0 to 64)
break from for loop;
end if
current = merge_lists(current, array[i]);
end for
end while

current = null;
for(i from 0 to 64)
if current is not null
else
end if
end if
end for



This is the algorithm that the linux kernel uses for sorting its linked lists. Though with some extra optimizations like ignoring the previous pointer during all but the last merge operation.

You can write merge sort , partition sort , tree sort and compare results
It is quite easy to write tree sort if you allow some extra space
For tree sort each node of linked list must have two pointers even if we sort singly linked list
Hoare partition can be done only for doubly linked list

program untitled;

type TData = longint;
PNode = ^TNode;
TNode = record
data:TData;
prev:PNode;
next:PNode;
end;

begin
end;

begin
end;

var x:PNode;
begin
while (x <> NIL)and(x^.data <> k)do
x := x^.next;
ListSearch := x;
end;

var x:PNode;
begin
new(x);
x^.data := k;
x^.prev := NIL;
end;

var x:PNode;
begin
if x <> NIL then
begin
if x^.prev <> NIL then
x^.prev^.next := x^.next
else
if x^.next <> NIL then
x^.next^.prev := x^.prev;
dispose(x);
end;
end;

var x:PNode;
counter:longint;
begin
counter := 0;
while x <> NIL do
begin
write(x^.data,' -> ');
x := x^.next;
counter := counter + 1;
end;
writeln('NIL');
writeln('Liczba elementow listy : ',counter);
end;

procedure BSTinsert(x:PNode;var t:PNode);
begin
if t = NIL then
t := x
else
if t^.data = x^.data then
BSTinsert(x,t^.prev)
else if t^.data < x^.data then
BSTinsert(x,t^.next)
else
BSTinsert(x,t^.prev);
end;

procedure BSTtoDLL(t:PNode;var L:PNode);
begin
if t <> NIL then
begin
BSTtoDLL(t^.next,L);
ListInsert(L,t^.data);
BSTtoDLL(t^.prev,L);
end;
end;

procedure BSTdispose(t:PNode);
begin
if t <> NIL then
begin
BSTdispose(t^.prev);
BSTdispose(t^.next);
dispose(t);
end;
end;

procedure BSTsort(var L:PNode);
var T,S:PNode;
x,xs:PNode;
begin
T := NIL;
S := NIL;
x := L;
while x <> NIL do
begin
xs := x^.next;
x^.prev := NIL;
x^.next := NIL;
BSTinsert(x,t);
x := xs;
end;
BSTtoDLL(T,S);
BSTdispose(T);
L := S;
end;

var i : byte;
k:TData;
BEGIN
repeat
writeln('0. Wyjscie');
writeln('1. Wstaw element na poczatek listy');
writeln('2. Usun element listy');
writeln('3. Posortuj elementy drzewem binarnym');
writeln('4. Wypisz elementy  listy');
case i of
0:
begin
end;
1:
begin
writeln('Podaj element jaki chcesz wstawic');
end;
2:
begin
writeln('Podaj element jaki chcesz usunac');
end;
3:
begin
end;
4:
begin
end
else
writeln('Brak operacji podaj inny numer');
end;
until i = 0;
END.


This code needs some improvements
Firstly we should limit extra storage to the recursion needs
then we should try to replace recursion with iteration
If we want to improve algorithm further we should use self balancing tree

• Thanks for your detailed contribution but this isn't a coding site. 200 lines of code doesn't do anything to explain why merge sort is preferred over quick sort for linked lists. May 18, 2018 at 17:28
• In partition Sort choosing pivot is limited to the first or last element (last if we keep pointer to the tail node) otherwise choosing pivot is slow Hoare partition is possible only for doubly linked lists Swapping should be replaced with inserting and deleting Tree sort with unbalanced tree has the same compexity as quicksort if we ignore constant factor but it is easier to avoid worst case in tree sort For merge sort there is to few characters in the comment May 18, 2018 at 19:43

Quicksort
Maybe I will show steps for quicksort

If list contains more than one node

1. Pivot selection
2. Partition list into three sublists
first sublist contains nodes with keys less than pivot key
second sublist contains nodes with keys equal to pivot key
third sublist contains nodes with keys greater than pivot key
3. Recursive calls for sublists which contain nodes not equal to pivot node
4. Concatenate sorted sublists into one sorted list

If we want to choose pivot fast the choice is limited
We can choose head node or tail node
Our list have to have poiner to the node if we want our pivot
be accessible fast otherwise we have to search for node