From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=ham autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: fd7c9,f142583de41ba830,start
X-Google-Attributes: gidfd7c9,public
X-Google-Thread: 108717,f142583de41ba830,start
X-Google-Attributes: gid108717,public
X-Google-Thread: 103376,f142583de41ba830,start
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,f142583de41ba830,start
X-Google-Attributes: gid1014db,public
X-Google-ArrivalTime: 2003-01-30 14:25:50 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: gomskams@yahoo.co.uk (goms)
Newsgroups: comp.lang.c,comp.lang.ada,comp.programming,comp.lang.forth
Subject: Quick Sort Median of Three worst case
Date: 30 Jan 2003 14:25:49 -0800
Organization: http://groups.google.com/
Message-ID: <588d8bf4.0301301425.586b0ae4@posting.google.com>
NNTP-Posting-Host: 170.215.122.172
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1043965549 31444 127.0.0.1 (30 Jan 2003 22:25:49
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 30 Jan 2003 22:25:49 GMT
Xref: archiver1.google.com comp.lang.c:170316 comp.lang.ada:33622
 comp.programming:50059 comp.lang.forth:30179
Date: 2003-01-30T22:25:49+00:00
List-Id: <comp.lang.ada>

Hi,

I would like to know the running time of the Median of Three routine
version Quick Sort for the following input

(a)      2, 3, 4, ..,N-1, N, 1

What is the running time for the following input

(b)      1, N, N-1, ....., 4, 3, 2

Is the above said inputs (a) and (b) the worst case? and is the
running time is O(N^2) ?

I know that using Median of Three routine version of Quick Sort for,

a) sorted input
  the pivot is always in the middle, so the time would be O(nlogn)

b) reverse-ordered input
  the pivot is always in the middle, so the time would be O(nlogn)


A reply with explanation will be great.  Thanks in Advance.