Greetings,
I would like to revisit the discussion and concur with John's perspective that
incremental progress through small, successive modifications is the appropriate
approach to move forward. Therefore, I would like to propose two distinct ideas
aimed at enhancing the functionality of insertion sort:
1. Implementation of a more efficient variant (as described in the introductory
part of this thread):
------------ OLD ------------
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
pl -= ST_POINTER_STEP)
DO_SWAP(pl, pl - ST_POINTER_STEP);
------------ NEW ------------
for (
pm = a + ST_POINTER_STEP;
pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP
) {
ST_POINTER_TYPE tmp = *pm;
for (
pl = pm - ST_POINTER_STEP;
pl >= a && DO_COMPARE(pl, &tmp) > 0;
pl -= ST_POINTER_STEP
)
*(pl + ST_POINTER_STEP) = *pl;
*(pl + ST_POINTER_STEP) = tmp;
}
------------
2. It appears that there is a consensus against disregarding the presorted
check, despite its questionable value. In light of this, an alternative
suggestion is to integrate the presorted check into the insertion sort path by
utilizing an unbounded insertion sort. Only after a maximum number of swaps
have occurred should we abandon the sorting process. If insertion sort is
executed on the entire array without any swaps, we can simply return. If not,
and we continue with quicksort after the swap limit has been reached, we at
least have left the array in a more sorted state, which may likely be
advantageous for subsequent iterations.
------------ OLD ------------
if (n < 7)
{
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) >
0;
pl -= ST_POINTER_STEP)
DO_SWAP(pl, pl - ST_POINTER_STEP);
return;
}
presorted = 1;
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
{
DO_CHECK_FOR_INTERRUPTS();
if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
{
presorted = 0;
break;
}
}
if (presorted)
return;
------------ NEW ------------
#define LIMIT_SWAPS 30 /* to be determined empirically */
int swaps = 0;
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
pl -= ST_POINTER_STEP) {
DO_SWAP(pl, pl - ST_POINTER_STEP);
if (++swaps == LIMIT_SWAPS)
goto quicksort;
}
if (swaps == 0)
return;
quicksort:
------------
Naturally, both modifications (with point 2 being highly speculative) are
currently independent of each other, and it is also crucial to benchmark the
combined variant as well as different values for LIMIT_SWAPS.
I would greatly appreciate assistance in benchmarking these proposed changes.
Your collaboration in this matter would be invaluable.
Cheers, Ben
