16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is no need to pick the last element as the pivot instead of the first $\endgroup$ – TheCppZoo Nov 13 '18 at 21:35
19
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ But the average time complexity is same right ? Using quick sort as well as merge sort for linked list . $\endgroup$ – Zephyr Nov 30 '17 at 21:07
  • 10
    $\begingroup$ @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. $\endgroup$ – Mark Nov 30 '17 at 23:59
  • $\begingroup$ @Zephyr Basically it's the difference of theoretical and empirical results. Empirically, quicksort is quicker. $\endgroup$ – ferit Dec 1 '17 at 5:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Stig Hemmer Dec 1 '17 at 8:39
  • 3
    $\begingroup$ 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. $\endgroup$ – Konrad Rudolph Dec 1 '17 at 13:31
4
$\begingroup$

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

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

current = null;
for(i from 0 to 64)
    if head_array[i] is not null
        if current is not null
            current = merge_lists(current, head_array[i]);
        else
            current = head_array[i];
        end if
     end if
 end for

 list.head = current;

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.

$\endgroup$
-2
$\begingroup$

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
In linked list i prefer inserting and deleting instead of swapping
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;

procedure ListInit(var head:PNode);
begin
  head := NIL;
end;

function ListIsEmpty(head:PNode):boolean;
begin
  ListIsEmpty := head = NIL;
end;

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

procedure ListInsert(var head:PNode;k:TData);
var x:PNode;
begin
  new(x);
  x^.data := k;
  x^.next := head;
  if head <> NIL then
     head^.prev := x;
   head := x;
   x^.prev := NIL;
end;

procedure ListDelete(var head:PNode;k:TData);
var x:PNode;
begin
   x := ListSearch(head,k);
   if x <> NIL then
   begin
     if x^.prev <> NIL then
        x^.prev^.next := x^.next
      else 
        head := x^.next;
     if x^.next <> NIL then
        x^.next^.prev := x^.prev;
     dispose(x);
   end;
end;

procedure ListPrint(head:PNode);
var x:PNode;
    counter:longint;
begin
  x := head;
  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;
    head:PNode;
    k:TData;
BEGIN
  ListInit(head);
  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');
     readln(i);
     case i of
     0:
     begin
       while not ListIsEmpty(head) do
            ListDelete(head,head^.data);
     end;
     1:
     begin
       writeln('Podaj element jaki chcesz wstawic');
       readln(k);
       ListInsert(head,k);
     end;
     2:
     begin
       writeln('Podaj element jaki chcesz usunac');
       readln(k);
       ListDelete(head,k);
     end;
     3:
     begin
       BSTsort(head);
     end;
     4:
     begin
        ListPrint(head);    
     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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby May 18 '18 at 17:28
  • $\begingroup$ 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 $\endgroup$ – Mariusz May 18 '18 at 19:43
-2
$\begingroup$

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

Ad 1.
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

Ad 2.
We can use queue operations for this step
Fist we dequeue node from original linked list
compare its key with pivot key and enqueue node to the correct sublist
Sublists are created from existing nodes and there is no need to
allocate memory for new nodes

Pointer to the tail node will be useful because queue operations
and concatenation run faster with presence of this pointer

$\endgroup$
  • $\begingroup$ I am afraid I could not see how this answers the question. $\endgroup$ – Apass.Jack Nov 23 '18 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.