Skip to content

Instantly share code, notes, and snippets.

@RobertDurfee

RobertDurfee/sorting_networks.c

Created December 16, 2021 19:51
Show Gist options
  • Save RobertDurfee/468373153e60ff7fed866f9c4d92e0ba to your computer and use it in GitHub Desktop.
Save RobertDurfee/468373153e60ff7fed866f9c4d92e0ba to your computer and use it in GitHub Desktop.
Download ZIP
Optimal serial software sorting networks for arrays with at most 16 elements.
Raw
sorting_networks.c
#define CE(A, B) \
if ((A) > (B)) { \
int tmp = (A); \
(A) = (B); \
(B) = tmp; \
}
void network2(int *start) {
CE(start[0], start[1]);
}
void network3(int *start) {
CE(start[0], start[2]);
CE(start[0], start[1]);
CE(start[1], start[2]);
}
void network4(int *start) {
CE(start[0], start[2]);
CE(start[1], start[3]);
CE(start[0], start[1]);
CE(start[2], start[3]);
CE(start[1], start[2]);
}
void network5(int *start) {
CE(start[0], start[3]);
CE(start[1], start[4]);
CE(start[0], start[2]);
CE(start[1], start[3]);
CE(start[0], start[1]);
CE(start[2], start[4]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[2], start[3]);
}
void network6(int *start) {
CE(start[0], start[5]);
CE(start[1], start[3]);
CE(start[2], start[4]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[0], start[3]);
CE(start[2], start[5]);
CE(start[0], start[1]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[1], start[2]);
CE(start[3], start[4]);
}
void network7(int *start) {
CE(start[0], start[6]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[0], start[2]);
CE(start[1], start[4]);
CE(start[3], start[6]);
CE(start[0], start[1]);
CE(start[2], start[5]);
CE(start[3], start[4]);
CE(start[1], start[2]);
CE(start[4], start[6]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[5], start[6]);
}
void network8(int *start) {
CE(start[0], start[2]);
CE(start[1], start[3]);
CE(start[4], start[6]);
CE(start[5], start[7]);
CE(start[0], start[4]);
CE(start[1], start[5]);
CE(start[2], start[6]);
CE(start[3], start[7]);
CE(start[0], start[1]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[2], start[4]);
CE(start[3], start[5]);
CE(start[1], start[4]);
CE(start[3], start[6]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[5], start[6]);
}
void network9(int *start) {
CE(start[0], start[3]);
CE(start[1], start[7]);
CE(start[2], start[5]);
CE(start[4], start[8]);
CE(start[0], start[7]);
CE(start[2], start[4]);
CE(start[3], start[8]);
CE(start[5], start[6]);
CE(start[0], start[2]);
CE(start[1], start[3]);
CE(start[4], start[5]);
CE(start[7], start[8]);
CE(start[1], start[4]);
CE(start[3], start[6]);
CE(start[5], start[7]);
CE(start[0], start[1]);
CE(start[2], start[4]);
CE(start[3], start[5]);
CE(start[6], start[8]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[5], start[6]);
}
void network10(int *start) {
CE(start[0], start[8]);
CE(start[1], start[9]);
CE(start[2], start[7]);
CE(start[3], start[5]);
CE(start[4], start[6]);
CE(start[0], start[2]);
CE(start[1], start[4]);
CE(start[5], start[8]);
CE(start[7], start[9]);
CE(start[0], start[3]);
CE(start[2], start[4]);
CE(start[5], start[7]);
CE(start[6], start[9]);
CE(start[0], start[1]);
CE(start[3], start[6]);
CE(start[8], start[9]);
CE(start[1], start[5]);
CE(start[2], start[3]);
CE(start[4], start[8]);
CE(start[6], start[7]);
CE(start[1], start[2]);
CE(start[3], start[5]);
CE(start[4], start[6]);
CE(start[7], start[8]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[3], start[4]);
CE(start[5], start[6]);
}
void network11(int *start) {
CE(start[0], start[9]);
CE(start[1], start[6]);
CE(start[2], start[4]);
CE(start[3], start[7]);
CE(start[5], start[8]);
CE(start[0], start[1]);
CE(start[3], start[5]);
CE(start[4], start[10]);
CE(start[6], start[9]);
CE(start[7], start[8]);
CE(start[1], start[3]);
CE(start[2], start[5]);
CE(start[4], start[7]);
CE(start[8], start[10]);
CE(start[0], start[4]);
CE(start[1], start[2]);
CE(start[3], start[7]);
CE(start[5], start[9]);
CE(start[6], start[8]);
CE(start[0], start[1]);
CE(start[2], start[6]);
CE(start[4], start[5]);
CE(start[7], start[8]);
CE(start[9], start[10]);
CE(start[2], start[4]);
CE(start[3], start[6]);
CE(start[5], start[7]);
CE(start[8], start[9]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[5], start[6]);
CE(start[7], start[8]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
}
void network12(int *start) {
CE(start[0], start[8]);
CE(start[1], start[7]);
CE(start[2], start[6]);
CE(start[3], start[11]);
CE(start[4], start[10]);
CE(start[5], start[9]);
CE(start[0], start[1]);
CE(start[2], start[5]);
CE(start[3], start[4]);
CE(start[6], start[9]);
CE(start[7], start[8]);
CE(start[10], start[11]);
CE(start[0], start[2]);
CE(start[1], start[6]);
CE(start[5], start[10]);
CE(start[9], start[11]);
CE(start[0], start[3]);
CE(start[1], start[2]);
CE(start[4], start[6]);
CE(start[5], start[7]);
CE(start[8], start[11]);
CE(start[9], start[10]);
CE(start[1], start[4]);
CE(start[3], start[5]);
CE(start[6], start[8]);
CE(start[7], start[10]);
CE(start[1], start[3]);
CE(start[2], start[5]);
CE(start[6], start[9]);
CE(start[8], start[10]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[8], start[9]);
CE(start[4], start[6]);
CE(start[5], start[7]);
CE(start[3], start[4]);
CE(start[5], start[6]);
CE(start[7], start[8]);
}
void network13(int *start) {
CE(start[0], start[12]);
CE(start[1], start[10]);
CE(start[2], start[9]);
CE(start[3], start[7]);
CE(start[5], start[11]);
CE(start[6], start[8]);
CE(start[1], start[6]);
CE(start[2], start[3]);
CE(start[4], start[11]);
CE(start[7], start[9]);
CE(start[8], start[10]);
CE(start[0], start[4]);
CE(start[1], start[2]);
CE(start[3], start[6]);
CE(start[7], start[8]);
CE(start[9], start[10]);
CE(start[11], start[12]);
CE(start[4], start[6]);
CE(start[5], start[9]);
CE(start[8], start[11]);
CE(start[10], start[12]);
CE(start[0], start[5]);
CE(start[3], start[8]);
CE(start[4], start[7]);
CE(start[6], start[11]);
CE(start[9], start[10]);
CE(start[0], start[1]);
CE(start[2], start[5]);
CE(start[6], start[9]);
CE(start[7], start[8]);
CE(start[10], start[11]);
CE(start[1], start[3]);
CE(start[2], start[4]);
CE(start[5], start[6]);
CE(start[9], start[10]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[5], start[7]);
CE(start[6], start[8]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[8], start[9]);
CE(start[3], start[4]);
CE(start[5], start[6]);
}
void network14(int *start) {
CE(start[0], start[6]);
CE(start[1], start[11]);
CE(start[2], start[12]);
CE(start[3], start[10]);
CE(start[4], start[5]);
CE(start[7], start[13]);
CE(start[8], start[9]);
CE(start[1], start[2]);
CE(start[3], start[7]);
CE(start[4], start[8]);
CE(start[5], start[9]);
CE(start[6], start[10]);
CE(start[11], start[12]);
CE(start[0], start[4]);
CE(start[1], start[3]);
CE(start[5], start[6]);
CE(start[7], start[8]);
CE(start[9], start[13]);
CE(start[10], start[12]);
CE(start[0], start[1]);
CE(start[2], start[9]);
CE(start[3], start[7]);
CE(start[4], start[11]);
CE(start[6], start[10]);
CE(start[12], start[13]);
CE(start[2], start[5]);
CE(start[4], start[7]);
CE(start[6], start[9]);
CE(start[8], start[11]);
CE(start[1], start[2]);
CE(start[3], start[4]);
CE(start[6], start[7]);
CE(start[9], start[10]);
CE(start[11], start[12]);
CE(start[1], start[3]);
CE(start[2], start[4]);
CE(start[5], start[6]);
CE(start[7], start[8]);
CE(start[9], start[11]);
CE(start[10], start[12]);
CE(start[2], start[3]);
CE(start[4], start[7]);
CE(start[6], start[9]);
CE(start[10], start[11]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[8], start[9]);
CE(start[3], start[4]);
CE(start[5], start[6]);
CE(start[7], start[8]);
CE(start[9], start[10]);
}
void network15(int *start) {
CE(start[1], start[2]);
CE(start[3], start[10]);
CE(start[4], start[14]);
CE(start[5], start[8]);
CE(start[6], start[13]);
CE(start[7], start[12]);
CE(start[9], start[11]);
CE(start[0], start[14]);
CE(start[1], start[5]);
CE(start[2], start[8]);
CE(start[3], start[7]);
CE(start[6], start[9]);
CE(start[10], start[12]);
CE(start[11], start[13]);
CE(start[0], start[7]);
CE(start[1], start[6]);
CE(start[2], start[9]);
CE(start[4], start[10]);
CE(start[5], start[11]);
CE(start[8], start[13]);
CE(start[12], start[14]);
CE(start[0], start[6]);
CE(start[2], start[4]);
CE(start[3], start[5]);
CE(start[7], start[11]);
CE(start[8], start[10]);
CE(start[9], start[12]);
CE(start[13], start[14]);
CE(start[0], start[3]);
CE(start[1], start[2]);
CE(start[4], start[7]);
CE(start[5], start[9]);
CE(start[6], start[8]);
CE(start[10], start[11]);
CE(start[12], start[13]);
CE(start[0], start[1]);
CE(start[2], start[3]);
CE(start[4], start[6]);
CE(start[7], start[9]);
CE(start[10], start[12]);
CE(start[11], start[13]);
CE(start[1], start[2]);
CE(start[3], start[5]);
CE(start[8], start[10]);
CE(start[11], start[12]);
CE(start[3], start[4]);
CE(start[5], start[6]);
CE(start[7], start[8]);
CE(start[9], start[10]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[7]);
CE(start[8], start[9]);
CE(start[10], start[11]);
CE(start[5], start[6]);
CE(start[7], start[8]);
}
void network16(int *start) {
CE(start[0], start[13]);
CE(start[1], start[12]);
CE(start[2], start[15]);
CE(start[3], start[14]);
CE(start[4], start[8]);
CE(start[5], start[6]);
CE(start[7], start[11]);
CE(start[9], start[10]);
CE(start[0], start[5]);
CE(start[1], start[7]);
CE(start[2], start[9]);
CE(start[3], start[4]);
CE(start[6], start[13]);
CE(start[8], start[14]);
CE(start[10], start[15]);
CE(start[11], start[12]);
CE(start[0], start[1]);
CE(start[2], start[3]);
CE(start[4], start[5]);
CE(start[6], start[8]);
CE(start[7], start[9]);
CE(start[10], start[11]);
CE(start[12], start[13]);
CE(start[14], start[15]);
CE(start[0], start[2]);
CE(start[1], start[3]);
CE(start[4], start[10]);
CE(start[5], start[11]);
CE(start[6], start[7]);
CE(start[8], start[9]);
CE(start[12], start[14]);
CE(start[13], start[15]);
CE(start[1], start[2]);
CE(start[3], start[12]);
CE(start[4], start[6]);
CE(start[5], start[7]);
CE(start[8], start[10]);
CE(start[9], start[11]);
CE(start[13], start[14]);
CE(start[1], start[4]);
CE(start[2], start[6]);
CE(start[5], start[8]);
CE(start[7], start[10]);
CE(start[9], start[13]);
CE(start[11], start[14]);
CE(start[2], start[4]);
CE(start[3], start[6]);
CE(start[9], start[12]);
CE(start[11], start[13]);
CE(start[3], start[5]);
CE(start[6], start[8]);
CE(start[7], start[9]);
CE(start[10], start[12]);
CE(start[3], start[4]);
CE(start[5], start[6]);
CE(start[7], start[8]);
CE(start[9], start[10]);
CE(start[11], start[12]);
CE(start[6], start[7]);
CE(start[8], start[9]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment