Here are some timings, in seconds, that compare the performance
of SRFI 132's reference implementation against the standard R6RS
sort procedures.

Average time for a list or vector containing 10000 elements:

R6RS list-sort         0.003395
list-sort              0.009694
list-stable-sort       0.003956
list-sort!             0.003656
list-stable-sort!      0.003648
R6RS vector-sort       0.003475
R6RS vector-sort!      0.00344
vector-sort            0.004775
vector-stable-sort     0.005019
vector-sort!           0.00473
vector-stable-sort!    0.00497
vector-find-median     0.003289
vector-find-median!    0.004738

Average time for a list or vector containing one million elements:

R6RS list-sort         0.570552
list-sort              1.532226
list-stable-sort       0.953935
list-sort!             0.606224
list-stable-sort!      0.596012
R6RS vector-sort       0.611689
R6RS vector-sort!      0.578449
vector-sort            0.764006
vector-stable-sort     0.766659
vector-sort!           0.759225
vector-stable-sort!    0.758613
vector-find-median     0.343902
vector-find-median!    0.7545

For all its complexity, the reference implementation never runs
quite as fast as Larceny's R6RS-conforming procedures.  Larceny
just uses Richard O'Keefe's code dating to 1991.  All three of
Larceny's R6RS sort procedures perform a stable merge sort.  The
two R6RS procedures that sort vectors immediately convert them
into lists, and convert back at the end.

Note also that Olin's stable list sort, which uses a merge sort,
is much faster than the reference implementation's unstable list
sort, which uses heapsort.

Note also that the destructive sorting routines of SRFI 132 are
slower than the non-destructive routines of R6RS, and (when the
unnecessarily slow heap sort is disregarded) the destructive
sort routines of SRFI 132 are only slightly faster than their
non-destructive counterparts.  You might expect the destructive
versions to look better in systems using a non-generational
garbage collector, but testing with Larceny's non-generational
stop-and-copy collector did not support that hypothesis.

The vector-find-median procedure is faster than the destructive
vector-find-median! because the non-destructive version doesn't
have to sort, and I took advantage of that in my implementation.
(Both of those procedures are missing from the reference
implementation, so I had to write them myself.)

One conclusion I draw is that the number of distinct sorting
routines specified by SRFI 132 cannot be justified on grounds
of performance or efficiency.

Will