Function tdigest_sort

pg_documentdb/src/aggregation/bson_tdigest.c:229–295

* Sort centroids in the digest. * * We have to sort the whole array, because we don't just simply sort the * centroids - we do the rebalancing of items with the same mean too. */

 * centroids - we do the rebalancing of items with the same mean too.
 */
static void
tdigest_sort(tdigest_aggstate_t *state)
{
	int i;
	int64 count_so_far;
	int64 next_group;
	int64 median_count;

	/* do qsort on the non-sorted part */
	pg_qsort(state->centroids,
			 state->ncentroids,
			 sizeof(centroid_t), centroid_cmp);

	/*
	 * The centroids are sorted by (mean,count). That's fine for centroids up
	 * to median, but above median this ordering is incorrect for centroids
	 * with the same mean (or for groups crossing the median boundary). To fix
	 * this we 'rebalance' those groups. Those entirely above median can be
	 * simply sorted in the opposite order, while those crossing the median
	 * need to be rebalanced depending on what part is below/above median.
	 */
	count_so_far = 0;
	next_group = 0; /* includes count_so_far */
	median_count = (state->count / 2);

	/*
	 * Split the centroids into groups with the same mean, process each group
	 * depending on whether it falls before/after median.
	 */
	i = 0;
	while (i < state->ncentroids)
	{
		int j = i;
		int group_size = 0;

		/* determine the end of the group */
		while ((j < state->ncentroids) &&
			   (state->centroids[i].mean == state->centroids[j].mean))
		{
			next_group += state->centroids[j].count;
			group_size++;
			j++;
		}

		/*
		 * We can ignore groups of size 1 (Total count of centroids, not counts), as
		 * those are trivially sorted.
		 */
		if (group_size > 1)
		{
			if (count_so_far >= median_count)
			{
				/* group fully above median - reverse the order */
				reverse_centroids(&state->centroids[i], group_size);
			}
			else if (next_group >= median_count)    /* group split by median */
			{
				rebalance_centroids(&state->centroids[i], group_size,