From: Victor Jetten <v DOT jetten AT frw DOT ruu DOT nl>
Newsgroups: comp.os.msdos.djgpp
Subject: fastest sort for an almost sorted array?
Date: Wed, 01 Apr 1998 14:25:23 +0200
Organization: Academic Computer Centre Utrecht, (ACCU)
Lines: 14
Message-ID: <35223233.53AD6263@frw.ruu.nl>
NNTP-Posting-Host: jetten.frw.ruu.nl
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Hi smart mathematicians,
I'm displaying a landscape in 3D, made out of quads that do not
intersect etc. Landscapes tend to be "well behaved", meaning not very
random with few occlusions. After 3D translation I sort the visible
polygons on distance with djgpp's quicksort. However, I can "pre-sort"
the array by assuming the landscape is flat and then make a smart
indexing so that the polygon farthest away is draw first. This is quick
and very dirty because obviuously there are height differences. What is
the fastest method to sort an almost sorted array? Is it still qsort?
any ideas are very welcome.

ciao Victor