Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!pyramid!pesnta!amd!amdcad!amdimage!prls!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <1246@mmintl.UUCP>
Date: Mon, 14-Apr-86 16:42:33 EST
Article-I.D.: mmintl.1246
Posted: Mon Apr 14 16:42:33 1986
Date-Received: Sat, 19-Apr-86 13:10:32 EST
References: <669@bentley.UUCP> <139200023@uiucdcsb> <695@bentley.UUCP>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT
Lines: 19

In article <695@bentley.UUCP> kwh@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