Sorting doubles with duplicates

[Graham]

Can someone point me to an algorithm for sorting double precision
values that is stable with duplicates?

Thanks,
Graham

 

[Mark McIntyre]

Can someone point me to an algorithm for sorting double precision
values that is stable with duplicates?

neither group you've posted to is appropriate for an algo question. Try
comp.programming, and consider converting the doubles to integers, or
implementing a sort based on rounding the values.

 

[Peter Ammon]

Can someone point me to an algorithm for sorting double precision
values that is stable with duplicates?

Thanks,
Graham

What's wrong with ordinary stable sorts, like mergesort?

 

[CBFalconer]

Can someone point me to an algorithm for sorting double precision
values that is stable with duplicates?

This belongs in comp.programming. F'ups set.

You are looking for mergesort. O(NlnN) and stable.

 

[pete]

Can someone point me to an algorithm for sorting double precision
values that is stable with duplicates?

/* BEGIN stable.h */
/* si_sort() and stable(), are both stable sorts. */

#ifndef H_STABLE
#define H_STABLE

#include <stddef.h>

#define E_TYPE long double
#define SMALL_MERGE 20

/*
** for merge and stable:
** Make SMALL_MERGE bigger for faster e_type
** Make SMALL_MERGE smaller for slower e_type
** eg. 40 for unsigned int, 20 for long double
** assert(SMALL_MERGE >= 1);
** SMALL_MERGE must be greater than or equal to one
*/
#define GT(A, B) (*(A) > *(B))

typedef E_TYPE e_type;

void si_sort(e_type *, size_t);
void stable(e_type *, size_t);

#endif

/* END stable.h */

/* BEGIN stable.c */
/* si_sort() and mgsort(), are both stable sorts. */

#include <stdlib.h>

#include "stable.h"

#define BUF_BYTES (128 * sizeof(int))

static int mgsort(e_type *, size_t);
static void merge(e_type *, e_type *, size_t);

void si_sort(e_type *array, size_t nmemb)
{
e_type temp, *base, *low, *high;

if (nmemb > 1) {
--nmemb;
base = array;
do {
low = array++;
if (GT(low, array)) {
high = array;
temp = *high;
do {
*high-- = *low;
if (low == base) {
break;
}
--low;
} while (GT(low, &temp));
*high = temp;
}
} while (--nmemb != 0);
}
}

void stable(e_type *array, size_t nmemb)
{
if (!(nmemb > SMALL_MERGE && mgsort(array, nmemb))) {
/*
** If mgsort() returns zero,
** then you may want to handle it differently.
*/
si_sort(array, nmemb);
}
}

static int mgsort(e_type *array, size_t nmemb)
{
e_type *buff;
e_type temp_array[BUF_BYTES > sizeof *array
? BUF_BYTES / sizeof *array : 1];

if (nmemb > sizeof temp_array / sizeof *temp_array * 2 + 1) {
buff = malloc(nmemb / 2 * sizeof *buff);
if (buff != NULL) {
merge(array, buff, nmemb);
free(buff);
} else {
return 0;
}
} else {
merge(array, temp_array, nmemb);
}
return 1;
}

static void merge(e_type *base, e_type *buff, size_t nmemb)
{
if (nmemb > SMALL_MERGE) {
e_type *mid_ptr;
size_t const half = nmemb / 2;
e_type *const middle = base + half;
e_type *const after_buff = buff + half;
e_type *const after_array = base + nmemb;

merge(middle, buff, nmemb - half);
merge(base, buff, half);
while (!(GT(base, middle) || middle == base)) {
++base;
}
buff = after_buff;
mid_ptr = middle;
while (base != mid_ptr) {
*--buff = *--mid_ptr;
}
mid_ptr = middle;
while (middle != base) {
*base++ = *(GT(buff, mid_ptr) ? mid_ptr++ : buff++);
}
while (after_buff != buff && after_array != mid_ptr) {
*base++ = *(GT(buff, mid_ptr) ? mid_ptr++ : buff++);
}
while (after_buff != buff) {
*base++ = *buff++;
}
} else {
si_sort(base, nmemb);
}
}

/* END stable.c */