Juan F. Meleiro

Prime Sort

I don't know if anyone thought of this before, though I strongly suspect that yes. The idea is very simple, after all. But here it is: a prime-based sorting algorithm.

This has a kindred spirit to sleep sort in the sense that is uses information about the list elements beyond their ordering.

Sleep sort uses the numbers in their cardinal sense (because they count time), and prime sort uses them in an ordinal sense (to index prime numbers).

Beyond that, the algorithm just uses that old and bad encoding trick where a multiset of natural numbers can be represented by multiplying some corresponding primes together. The Fundamental Theorem of Arithmetic implies the original multiset can be recovered. Their order, however, cannot, because of commutativity of arithmetic multiplication – hence the sorting.

Here's the pseudo-code:

acc ← 1

for each n in the input:
  acc ← acc * nth_prime(n)

for each slot in the output:
  try to divide acc by each prime
  when succeeded with the n-th prime p:
    acc ← acc / p
    output n

Here's some actual code:

#include 
#include 
#include 
#include 

bool is_prime(long long unsigned int n) {
	for (long long unsigned int k = 2; k*k <= n; k++)
		if (n % k == 0) return false;
	return true;
}

long long unsigned int nth_prime(int n)
{
	long long unsigned int candidate = 2;
	int count = 0;
	for (int count = 0; count < n; count++) {
		/* Invariant: candidate is the n-th prime. */
		assert(is_prime(candidate));
		assert(count < n);
		candidate++;
		while (!is_prime(candidate)) candidate++;
	}
	assert(is_prime(candidate));
	return candidate;
}

void prime_sort(unsigned int *list, size_t len)
{
	long long unsigned int acc = 1;

	/* Pack */
	for (size_t i = 0; i < len; i++)
		acc *= nth_prime(list[i]);

	/* Unpack */
	size_t list_index = 0;
	int prime_index = 0;
	while (list_index < len) {
		assert(acc > 1);
		long long unsigned int p = nth_prime(prime_index);
		if (acc % p == 0) {
			acc = acc / p;
			list[list_index] = prime_index;
			list_index++;
		} else {
			prime_index++;
		}
	}

	assert(acc == 1);
}

int main(void)
{
	int list[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

	prime_sort(list, 10);

	for (size_t i = 0; i < 10; i++)
		printf("%s%d", i > 0 ? "," : "", list[i]);
	printf("\n");
}