Sorting linked list

[Frank Adams]

In article <695 at bentley.UUCP> kwh at bentley.UUCP writes:
>Is it possible to implement a quicksort on a linked list directly?  (Just
>wondering; I don't think it would be an improvement on the posted merge
>sort, which is already O(n log n) time and O(1) space.)

(1) Yes, it is certainly possible.

(2) No, it isn't an improvement over merge sort for linked lists.  It is
    also expensive to do the usual sort of worst-case reduction (by taking
    median of first, last, and middle as the separator value) which is common
    for quick sort.  Without this kind of optimization, quick-sort is
    O(n^2) on lists which are already sorted.  (It remains O(n^2) worst
    case, but the worst case becomes much less common.)

(3) The posted merge sort is O(log n) space.  You have to count stack space,
    and it recurses to depth O(log n).

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108