How to implement quicksort on a double-linked list of pointers?

Question

I have the code for quicksorting an array of pointers (if helps anyone) but how I do that for a doble linked list of pointers ?

procedure TSuperList.Sort;
begin
 if Assigned(FOnCompare) and (Length(Items)>1) then
  QuickSort(0,High(Items));
end;

procedure TSuperList.QuickSort(L,R:Integer);
var I,J: Integer;
    P,T: Pointer;
begin
  repeat
    I:=L;
    J:=R;
    P:=Items[(L+R) shr 1];
    repeat
      while FOnCompare(self,Items[I],P) < 0 do Inc(I);
      while FOnCompare(self,Items[J],P) > 0 do Dec(J);
      if I <= J then begin
        if I <> J then begin
          T:=Items[I]; Items[I]:=Items[J]; Items[J]:=T;
        end;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then QuickSort(L,J);
    L:=I;
  until I >= R;
end;

Answer 1

Quicksort is a good choice when you can use O(1) random access. Otherwise it's a not a good choice.

You can certainly implement Quicksort with your doubly linked list. It's just that any time you need random access to an element, you need to step through your list. Clearly that is going to destroy performance. Much of the Quicksort algorithm does not need random access. Those parts of the algorithm exemplified by Inc and Dec statements are trivial for lists. But the problem is pivot choice. In your code above that is this line:

P:=Items[(L+R) shr 1];

Whilst you can clearly implement that for a list, it is inefficient.

For a linked list, the efficient choice of searching algorithm is Mergesort. An excerpt from that Wikipedia page says:

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.