[1/2] Ensure qsort recursion depth is bounded

Message ID HE1PR07MB31778C985EFBC8444BC30EA29FD30@HE1PR07MB3177.eurprd07.prod.outlook.com
State Accepted
Commit 0045445ad6f5d2271d677fa77f896b549485e581
Headers show
Series
  • [1/2] Ensure qsort recursion depth is bounded
Related show

Commit Message

Håkan Lindqvist March 12, 2018, 3:44 p.m.
From 9d2f1fc59b8338f54c13dba4dac01d8751ceb8df Mon Sep 17 00:00:00 2001
From: Hakan Lindqvist <hakan.lindqvist@enea.com>

Date: Mon, 12 Mar 2018 13:51:07 +0100
Subject: [PATCH 1/2] Ensure qsort recursion depth is bounded

The qsort algorithm splits the input array in three parts. The
left and right parts may need further sorting. One of them is
sorted by recursion, the other by iteration. This update ensures
that it is the smaller part that is chosen for recursion.

By choosing the smaller part, each recursion level will handle
less than half the array of the previous recursion level. Hence
the recursion depth is bounded to be less than log2(n) i.e. 1
level per significant bit in the array size n.

The update also includes code comments explaining the algorithm.
---
 newlib/libc/search/qsort.c | 68 ++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 56 insertions(+), 12 deletions(-)

-- 
1.8.5

Comments

Corinna Vinschen March 13, 2018, 12:53 p.m. | #1
On Mar 12 15:44, Håkan Lindqvist wrote:
> From 9d2f1fc59b8338f54c13dba4dac01d8751ceb8df Mon Sep 17 00:00:00 2001

> From: Hakan Lindqvist <hakan.lindqvist@enea.com>

> Date: Mon, 12 Mar 2018 13:51:07 +0100

> Subject: [PATCH 1/2] Ensure qsort recursion depth is bounded

> 

> The qsort algorithm splits the input array in three parts. The

> left and right parts may need further sorting. One of them is

> sorted by recursion, the other by iteration. This update ensures

> that it is the smaller part that is chosen for recursion.

> 

> By choosing the smaller part, each recursion level will handle

> less than half the array of the previous recursion level. Hence

> the recursion depth is bounded to be less than log2(n) i.e. 1

> level per significant bit in the array size n.

> 

> The update also includes code comments explaining the algorithm.


The patch looks good at first glance.  Would you mind to outline how
you tested it?


Thanks,
Corinna

> ---

>  newlib/libc/search/qsort.c | 68 ++++++++++++++++++++++++++++++++++++++--------

>  1 file changed, 56 insertions(+), 12 deletions(-)

> 

> diff --git a/newlib/libc/search/qsort.c b/newlib/libc/search/qsort.c

> index db3f589..4dc61be 100644

> --- a/newlib/libc/search/qsort.c

> +++ b/newlib/libc/search/qsort.c

> @@ -173,15 +173,18 @@ qsort (void *a,

>  	int cmp_result;

>  	int swaptype, swap_cnt;

>  

> -loop:	SWAPINIT(a, es);

> -	swap_cnt = 0;

> +	SWAPINIT(a, es);

> +loop:	swap_cnt = 0;

>  	if (n < 7) {

> +		/* Short arrays are insertion sorted. */

>  		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)

>  			for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;

>  			     pl -= es)

>  				swap(pl, pl - es);

>  		return;

>  	}

> +

> +	/* Select a pivot element, move it to the left. */

>  	pm = (char *) a + (n / 2) * es;

>  	if (n > 7) {

>  		pl = a;

> @@ -195,11 +198,17 @@ loop:	SWAPINIT(a, es);

>  		pm = med3(pl, pm, pn, cmp, thunk);

>  	}

>  	swap(a, pm);

> -	pa = pb = (char *) a + es;

>  

> +	/*

> +	 * Sort the array relative the pivot in four ranges as follows:

> +	 * { elems == pivot, elems < pivot, elems > pivot, elems == pivot }

> +	 */

> +	pa = pb = (char *) a + es;

>  	pc = pd = (char *) a + (n - 1) * es;

>  	for (;;) {

> +		/* Scan left to right stopping at first element > pivot. */

>  		while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {

> +			/* Move elements == pivot to the left (to pa) */

>  			if (cmp_result == 0) {

>  				swap_cnt = 1;

>  				swap(pa, pb);

> @@ -207,7 +216,9 @@ loop:	SWAPINIT(a, es);

>  			}

>  			pb += es;

>  		}

> +		/* Scan right to left stopping at first element < pivot. */

>  		while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {

> +			/* Move elements == pivot to the right (to pd) */

>  			if (cmp_result == 0) {

>  				swap_cnt = 1;

>  				swap(pc, pd);

> @@ -217,6 +228,7 @@ loop:	SWAPINIT(a, es);

>  		}

>  		if (pb > pc)

>  			break;

> +		/* The scan has found two elements to swap with each other. */

>  		swap(pb, pc);

>  		swap_cnt = 1;

>  		pb += es;

> @@ -230,24 +242,56 @@ loop:	SWAPINIT(a, es);

>  		return;

>  	}

>  

> +	/*

> +	 * Rearrange the array in three parts sorted like this:

> +	 * { elements < pivot, elements == pivot, elements > pivot }

> +	 */

>  	pn = (char *) a + n * es;

>  	r = min(pa - (char *)a, pb - pa);

>  	vecswap(a, pb - r, r);

>  	r = min(pd - pc, pn - pd - es);

>  	vecswap(pb, pn - r, r);

> -	if ((r = pb - pa) > es)

> +	d = pb - pa; /* d = Size of left part. */

> +	r = pd - pc; /* r = Size of right part. */

> +	pn -= r;     /* pn = Base of right part. */

> +

> +	/*

> +	 * Check which of the left and right parts are larger.

> +	 * Set (a, n)  to (base, size) of the larger part.

> +	 * Set (pa, r) to (base, size) of the smaller part.

> +	 */

> +	if (r > d) { /* Right part is the larger part */

> +		pa = a;

> +		a = pn;

> +		n = r;

> +		r = d;

> +	}

> +	else { /* Left part is the larger part, or both are equal. */

> +		pa = pn;

> +		n = d;

> +	}

> +

> +	/*

> +	 * The left and right parts each need further sorting if they

> +	 * contain two elements or more. If both need sorting we use

> +	 * recursion to sort the smaller part and save the larger part

> +	 * to be sorted by iteration after the recursion.

> +	 * Using recursion only for the smaller part guarantees a

> +	 * recursion depth that is bounded to be less than (log2(n)).

> +	 */

> +	if (r > es) {  /* Smaller part > 1 element. Both parts need sorting. */

> +		/* Sort smaller part using recursion. */

>  #if defined(I_AM_QSORT_R)

> -		__bsd_qsort_r(a, r / es, es, thunk, cmp);

> +		__bsd_qsort_r(pa, r / es, es, thunk, cmp);

>  #elif defined(I_AM_GNU_QSORT_R)

> -		qsort_r(a, r / es, es, cmp, thunk);

> +		qsort_r(pa, r / es, es, cmp, thunk);

>  #else

> -		qsort(a, r / es, es, cmp);

> +		qsort(pa, r / es, es, cmp);

>  #endif

> -	if ((r = pd - pc) > es) {

> -		/* Iterate rather than recurse to save stack space */

> -		a = pn - r;

> -		n = r / es;

> +	}

> +	if (n > es) {  /* The larger part needs sorting. Iterate to sort.  */

> +		n = n / es;

>  		goto loop;

>  	}

> -/*		qsort(pn - r, r / es, es, cmp);*/

> +	/* Both left and right parts are one element or less - level done. */

>  }

> -- 

> 1.8.5


-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat
Håkan Lindqvist March 14, 2018, 5:54 p.m. | #2
> -----Original Message-----

> From: Corinna Vinschen <vinschen@redhat.com>

> Sent: den 13 mars 2018 13:53

> To: newlib@sourceware.org

> Cc: Håkan Lindqvist <hakan.lindqvist@enea.com>

> Subject: Re: [PATCH 1/2] Ensure qsort recursion depth is bounded

> 

> On Mar 12 15:44, Håkan Lindqvist wrote:

> > From 9d2f1fc59b8338f54c13dba4dac01d8751ceb8df Mon Sep 17 00:00:00

> 2001

> > From: Hakan Lindqvist <hakan.lindqvist@enea.com>

> > Date: Mon, 12 Mar 2018 13:51:07 +0100

> > Subject: [PATCH 1/2] Ensure qsort recursion depth is bounded

> >

> > The qsort algorithm splits the input array in three parts. The left

> > and right parts may need further sorting. One of them is sorted by

> > recursion, the other by iteration. This update ensures that it is the

> > smaller part that is chosen for recursion.

> >

> > By choosing the smaller part, each recursion level will handle less

> > than half the array of the previous recursion level. Hence the

> > recursion depth is bounded to be less than log2(n) i.e. 1 level per

> > significant bit in the array size n.

> >

> > The update also includes code comments explaining the algorithm.

> 

> The patch looks good at first glance.  Would you mind to outline how you

> tested it?

> 


I wrote a test program, It mostly tests sorting random data, but also specific patterns. I'll include it below. 
It's not "production quality"; there is lots of stuff from when I was testing different things. Sorry about that.

You can use command line arguments to select different patterns. Mostly random patterns, but also special pattern using negative -r values.

The program contains ifdeffed stuff. Some of it is for timing measurements with facilities from the OS we make. Other parts are some measurement probe stuff another version of qsort that I used to verify the recursion depth, and for when I was experimenting with other another patch.

Best regards
Håkan Lindqvist

---- TEST PROGRAM BELOW ---


#include "stdlib.h"
#include "stdio.h"
#include "stdint.h"
#include "assert.h"
#include "errno.h"
#include "string.h"

#include "getopt.h"

#ifdef USE_OSE_HWTIMER
#include "ose.h"
#include "hwtimer.h"
#include "cpu_access.h"
#endif


#ifdef USE_DEBUG_PROBE
/* Debug probe variables */
extern size_t qsort_peak_recursion;
extern size_t qsort_combined_recursion;
extern size_t qsort_insertion_count;
extern size_t qsort_disable_insertion;
extern size_t qsort_insertion_threshold;
/* Measurements */
static size_t max_peak_recursion;
#endif


#ifdef USE_OSE_HWTIMER
/* Timer */
static unsigned long hw_handle;
static uint32_t hw_freq;
#endif


/* Options */
static int verbose_level = 0;
static size_t set_size =   10000;
static int data_range =    100000;
static size_t data_stride = 1;
static uint32_t compare_delay = 0;

/* Data set */
static int *data_array;


/* Compare-function for integers */
static int
int_comp(const void *ap, const void *bp)
{
   volatile uint32_t count;
   int a = *(const int *)ap;
   int b = *(const int *)bp;
   if (compare_delay != 0)
      for (count = 0; count < compare_delay; count++) { ; }
   return (a < b) ? -1 : (a == b) ? 0 : 1;
}

static uint64_t
test_once(void)
{
   size_t i, j;
   uint64_t us = 0;
#ifdef USE_OSE_HWTIMER
   uint32_t hw_time;
#endif

   if (data_range <= 0)
   {
      if (data_range == 0)
      {
         /* Sequential sorted data */
         for (i = 0; i < set_size;)
         {
            int data = i;
            size_t stride = 1 + rand() % data_stride;
            for (j = 0; i < set_size && j < stride; i++, j++)
               data_array[i] = data;
         }
      }
      else if (data_range == -1)
      {
         /* Best case for inserion sort */
         for (i = 0; i < set_size; i++)
            data_array[i] = i;
         data_array[0] = set_size/2-1;
      }
      else if (data_range == -2)
      {
         /* Worst case for the insertion sort */
         data_array[0] = set_size - 1;
         data_array[set_size / 2] = set_size;
         for (i = 1; i < (set_size / 2); i++)
         {
            data_array[i] = set_size / 2 - i;
            data_array[i + set_size / 2] = set_size * 2 - i;
         }
      }
      else if (data_range == -3)
      {
         for (i = 0; i < set_size; i++)
            data_array[i] = set_size - i;
         data_array[0] = set_size/2-1;
      }
      else if (data_range == -4)
      {
         for (i = 0; i < set_size; i++)
            data_array[i] = set_size - i;
      }
      else
      {
         for (i = 0; i < (set_size / 2); i++)
            data_array[i] = 0;
         data_array[i++] = 1;
         for (; i < set_size; i++)
            data_array[i] = 2;
      }
   }
   else
   {
      /* Initialize array with random data */
      for (i = 0; i < set_size;)
      {
         int data = rand() % data_range;
         size_t stride = 1 + rand() % data_stride;
         for (j = 0; i < set_size && j < stride; i++, j++)
            data_array[i] = data;
      }
   }

#ifdef USE_DEBUG_PROBE
   qsort_peak_recursion = 0;
   qsort_combined_recursion = 0;
   qsort_insertion_count = 0;
#endif

#ifdef USE_OSE_HWTIMER
   hw_time = hwtimer_read(hw_handle);
#endif

   /* Sort */
   qsort(data_array, set_size, sizeof(int), &int_comp);

#ifdef USE_OSE_HWTIMER
   hw_time = hwtimer_read(hw_handle) - hw_time;
   us = (hw_time * UINT64_C(1000000)) / hw_freq;
#endif

#ifdef USE_DEBUG_PROBE
   if (verbose_level != 0)
      printf("recursion=%2lu, ins_count=%2lu, us=%8llu\n",
             qsort_peak_recursion, qsort_insertion_count, us);

   if (max_peak_recursion < qsort_peak_recursion)
      max_peak_recursion = qsort_peak_recursion;

   assert(qsort_combined_recursion == 0);
#endif

   /* Validate result */
   for (i = 1; i < set_size; i++)
      if (data_array[i-1] > data_array[i])
      {
         printf("Sort failure: data_range=%lu, set_size=%lu, i=%lu\n",
               data_range, set_size, i);
         exit(-1);
      }

   return us;
}


struct Suffix { char suffix; long factor; };

static const struct Suffix bytecount_suffixes[] = {
   { 'B', 1 },
   { 'K', 1024 },
   { 'M', 1024*1024 },
   { 'G', 1024*1024*1024 },
   { 0 }
};

/*
*  Parse an argument string as a set of numbers with suffixes.
*  E.g. 1h30m with time_suffixes is 1*60*60 + 30*60 = 5400.
*  returns -1 in case of failure.
*/
static long
parsearg(const char *arg, const struct Suffix *suffixes)
{
   long value = 0;
   long part;
   const char *str = arg;
   char *endptr;
   const struct Suffix *s;

   for (;;)
   {
      part = strtol(str, &endptr, 0);
      if (endptr == str)
         goto fail;  /* No subject part of the number */
      str = endptr;

      if (*str != '\0')
      {
         for (s = suffixes; ; s++)
         {
            if (s == NULL || s->suffix == 0)
               goto fail;  /* No recognized suffix */
            if (*str == s->suffix)
            {
               part *= s->factor;
               str++;
               break;
            }
         }
      }

      value += part;

      if (*str == '\0')
         return value;     /* Reached end of argument with no errors. */
   }
 fail:
   fprintf(stderr, "Unrecognized option argument: %s\n", arg);
   if (errno == 0)
      errno = EINVAL;
   return -1;
}


int
main(int argc, char *argv[])
{
   uint64_t measure_set[2][12];
   int c = 0;

   /* Parse options. */
   while (c != -1)
   {
      static const struct option longopts[] =
      {
         { "verbose", no_argument, 0, 'v' },
         { "set", required_argument, 0, 's' },
         { "range", required_argument, 0, 'r' },
         { "stride", required_argument, 0, 'd' },
         { "delay", required_argument, 0, 'y' },
         { 0 }
      };
      errno = 0;
      c = getopt_long (argc, argv, "vqnt:s:r:p:c:i:m:d:", longopts, NULL);
      switch (c)
      {
         case -1:   /* No more options */
            break;
         case 'v':            /* Option "--verbose" */
            verbose_level = 1;
            break;
         case 's':
            set_size = parsearg(optarg, bytecount_suffixes);
            break;
         case 'r':
            data_range = parsearg(optarg, bytecount_suffixes);
            break;
         case 'd':
            data_stride = parsearg(optarg, bytecount_suffixes);
            break;
         case 'y':
            compare_delay = parsearg(optarg, bytecount_suffixes);
            break;
         default:
            fprintf(stderr, "Unknown option %d\n", c);
      }
      if (errno != 0)
      {
         fprintf(stderr, "Option error %s", strerror(errno));
         exit(-1);
      }
   }
   
   data_array = malloc(set_size * sizeof(int));
   if (data_array == NULL)
   {
      printf("malloc of data_array failed.\n");
      return -1;
   }

#ifdef USE_OSE_HWTIMER
   /* Prepare hwtimer */
   hw_handle = biosOpen(HWTIMER_BIOSNAME);
   hw_freq = hwtimer_freq(hw_handle, -1);
#endif

#ifdef USE_DEBUG_PROBE
   for (qsort_insertion_threshold = 2;
        qsort_insertion_threshold < 12;
        qsort_insertion_threshold++)
   {
      for (qsort_disable_insertion = 0;
           qsort_disable_insertion < 2;
           qsort_disable_insertion++)
      {
         srand(1);
         measure_set[qsort_disable_insertion][qsort_insertion_threshold] =
            test_once();
      }
   }
#else
   srand(1);
   measure_set[0][0] =
      test_once();
#endif

   printf("-s set_size = %lu\n", set_size);
   printf("-r data_range = %i\n", data_range);
   printf("-d data_stride = %lu\n", data_stride);
   printf("-l compare_delay = %lu\n", compare_delay);


#ifdef USE_OSE_HWTIMER
#ifdef USE_DEBUG_PROBE
   printf("\nmax_recursion = %lu\n\n", max_peak_recursion);
   printf("Thresh  Insertion  No Insertion\n");
   for (qsort_insertion_threshold = 2;
        qsort_insertion_threshold < 12;
        qsort_insertion_threshold++)
   {
      printf("%-8d%9llu%9llu\n",
             qsort_insertion_threshold,
             measure_set[0][qsort_insertion_threshold],
             measure_set[1][qsort_insertion_threshold]);
   }
#else
   printf("microseconds: %llu\n", measure_set[0][0]);
#endif
#endif

   return 0;
}
Corinna Vinschen March 16, 2018, 9:32 a.m. | #3
On Mar 14 17:54, Håkan Lindqvist wrote:
> > -----Original Message-----

> > From: Corinna Vinschen <vinschen@redhat.com>

> > Sent: den 13 mars 2018 13:53

> > To: newlib@sourceware.org

> > Cc: Håkan Lindqvist <hakan.lindqvist@enea.com>

> > Subject: Re: [PATCH 1/2] Ensure qsort recursion depth is bounded

> > 

> > On Mar 12 15:44, Håkan Lindqvist wrote:

> > > From 9d2f1fc59b8338f54c13dba4dac01d8751ceb8df Mon Sep 17 00:00:00

> > 2001

> > > From: Hakan Lindqvist <hakan.lindqvist@enea.com>

> > > Date: Mon, 12 Mar 2018 13:51:07 +0100

> > > Subject: [PATCH 1/2] Ensure qsort recursion depth is bounded

> > >

> > > The qsort algorithm splits the input array in three parts. The left

> > > and right parts may need further sorting. One of them is sorted by

> > > recursion, the other by iteration. This update ensures that it is the

> > > smaller part that is chosen for recursion.

> > >

> > > By choosing the smaller part, each recursion level will handle less

> > > than half the array of the previous recursion level. Hence the

> > > recursion depth is bounded to be less than log2(n) i.e. 1 level per

> > > significant bit in the array size n.

> > >

> > > The update also includes code comments explaining the algorithm.

> > 

> > The patch looks good at first glance.  Would you mind to outline how you

> > tested it?

> > 

> 

> I wrote a test program, It mostly tests sorting random data, but also specific patterns. I'll include it below. 

> It's not "production quality"; there is lots of stuff from when I was testing different things. Sorry about that.

> 

> You can use command line arguments to select different patterns. Mostly random patterns, but also special pattern using negative -r values.

> 

> The program contains ifdeffed stuff. Some of it is for timing measurements with facilities from the OS we make. Other parts are some measurement probe stuff another version of qsort that I used to verify the recursion depth, and for when I was experimenting with other another patch.


Patchset pushed.


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

Patch

diff --git a/newlib/libc/search/qsort.c b/newlib/libc/search/qsort.c
index db3f589..4dc61be 100644
--- a/newlib/libc/search/qsort.c
+++ b/newlib/libc/search/qsort.c
@@ -173,15 +173,18 @@  qsort (void *a,
 	int cmp_result;
 	int swaptype, swap_cnt;
 
-loop:	SWAPINIT(a, es);
-	swap_cnt = 0;
+	SWAPINIT(a, es);
+loop:	swap_cnt = 0;
 	if (n < 7) {
+		/* Short arrays are insertion sorted. */
 		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
 			for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
 			     pl -= es)
 				swap(pl, pl - es);
 		return;
 	}
+
+	/* Select a pivot element, move it to the left. */
 	pm = (char *) a + (n / 2) * es;
 	if (n > 7) {
 		pl = a;
@@ -195,11 +198,17 @@  loop:	SWAPINIT(a, es);
 		pm = med3(pl, pm, pn, cmp, thunk);
 	}
 	swap(a, pm);
-	pa = pb = (char *) a + es;
 
+	/*
+	 * Sort the array relative the pivot in four ranges as follows:
+	 * { elems == pivot, elems < pivot, elems > pivot, elems == pivot }
+	 */
+	pa = pb = (char *) a + es;
 	pc = pd = (char *) a + (n - 1) * es;
 	for (;;) {
+		/* Scan left to right stopping at first element > pivot. */
 		while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
+			/* Move elements == pivot to the left (to pa) */
 			if (cmp_result == 0) {
 				swap_cnt = 1;
 				swap(pa, pb);
@@ -207,7 +216,9 @@  loop:	SWAPINIT(a, es);
 			}
 			pb += es;
 		}
+		/* Scan right to left stopping at first element < pivot. */
 		while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
+			/* Move elements == pivot to the right (to pd) */
 			if (cmp_result == 0) {
 				swap_cnt = 1;
 				swap(pc, pd);
@@ -217,6 +228,7 @@  loop:	SWAPINIT(a, es);
 		}
 		if (pb > pc)
 			break;
+		/* The scan has found two elements to swap with each other. */
 		swap(pb, pc);
 		swap_cnt = 1;
 		pb += es;
@@ -230,24 +242,56 @@  loop:	SWAPINIT(a, es);
 		return;
 	}
 
+	/*
+	 * Rearrange the array in three parts sorted like this:
+	 * { elements < pivot, elements == pivot, elements > pivot }
+	 */
 	pn = (char *) a + n * es;
 	r = min(pa - (char *)a, pb - pa);
 	vecswap(a, pb - r, r);
 	r = min(pd - pc, pn - pd - es);
 	vecswap(pb, pn - r, r);
-	if ((r = pb - pa) > es)
+	d = pb - pa; /* d = Size of left part. */
+	r = pd - pc; /* r = Size of right part. */
+	pn -= r;     /* pn = Base of right part. */
+
+	/*
+	 * Check which of the left and right parts are larger.
+	 * Set (a, n)  to (base, size) of the larger part.
+	 * Set (pa, r) to (base, size) of the smaller part.
+	 */
+	if (r > d) { /* Right part is the larger part */
+		pa = a;
+		a = pn;
+		n = r;
+		r = d;
+	}
+	else { /* Left part is the larger part, or both are equal. */
+		pa = pn;
+		n = d;
+	}
+
+	/*
+	 * The left and right parts each need further sorting if they
+	 * contain two elements or more. If both need sorting we use
+	 * recursion to sort the smaller part and save the larger part
+	 * to be sorted by iteration after the recursion.
+	 * Using recursion only for the smaller part guarantees a
+	 * recursion depth that is bounded to be less than (log2(n)).
+	 */
+	if (r > es) {  /* Smaller part > 1 element. Both parts need sorting. */
+		/* Sort smaller part using recursion. */
 #if defined(I_AM_QSORT_R)
-		__bsd_qsort_r(a, r / es, es, thunk, cmp);
+		__bsd_qsort_r(pa, r / es, es, thunk, cmp);
 #elif defined(I_AM_GNU_QSORT_R)
-		qsort_r(a, r / es, es, cmp, thunk);
+		qsort_r(pa, r / es, es, cmp, thunk);
 #else
-		qsort(a, r / es, es, cmp);
+		qsort(pa, r / es, es, cmp);
 #endif
-	if ((r = pd - pc) > es) {
-		/* Iterate rather than recurse to save stack space */
-		a = pn - r;
-		n = r / es;
+	}
+	if (n > es) {  /* The larger part needs sorting. Iterate to sort.  */
+		n = n / es;
 		goto loop;
 	}
-/*		qsort(pn - r, r / es, es, cmp);*/
+	/* Both left and right parts are one element or less - level done. */
 }