[r6rs-discuss] [Formal] Request for reconsideration (in part) of formal comment #47

From: William D Clinger <will>
Date: Mon Jan 22 19:37:24 2007

I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors, and
this message should not be confused with the editors'
eventual formal response.

John Cowan wrote:
> Providing vector-sort! as primitive will alleviate this requirement.
> It is very easy to define vector-sort on top of it by copying the source
> vector and destructively sorting the copy.

As specified in 5.92, vector-sort is stable. Although
a destructive in-place sort (i.e. one that requires
only O(1) additional space) can be both stable and
O(n lg n) time, it is my impression that the constant
factors for those algorithms are large, and that the
fastest algorithms for in-place sorting are unstable.

If my impression is correct, then I think it would be
best to add vector-sort! as a third sorting primitive,
and allow it to use algorithms such as randomized
quicksort (unstable, with O(n^2) time in the worst
case), while continuing to require vector-sort and
list-sort to perform an O(n lg n) stable sort.

Will
Received on Mon Jan 22 2007 - 19:37:18 UTC