Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!purdue!haven!adm!smoke!gwyn
From: gwyn@smoke.BRL.MIL (Doug Gwyn)
Newsgroups: comp.lang.c
Subject: Re: sort
Message-ID: <10488@smoke.BRL.MIL>
Date: 6 Jul 89 16:17:16 GMT
References: <166@stsim.UUCP> <4700040@m.cs.uiuc.edu> <770@ocsmd.ocs.com> <422@siswat.UUCP>
Reply-To: gwyn@brl.arpa (Doug Gwyn)
Organization: Ballistic Research Lab (BRL), APG, MD.
Lines: 12

In article <422@siswat.UUCP> buck@siswat.UUCP (A. Lester Buck) writes:
>But this [merge sorting with replacement selection] is definitely
>_not_ what Unix sort does, using qsort(3) for all sorts.

As of SVR2, the UNIX "sort" utility definitely did perform n-way merge
sorting with replacement selection.  It used a binary tree for each of
the internal runs being merged, inserting a fresh record from an
external merge input file after each merged record was output.  A
quicksort algorithm (not qsort() from the C library, however) was used
only to produce the initial internal runs.

When did this change?