Micha Mettke vurtun
igorburago
/ partsort.c
Last active
October 21, 2025 16:14
Fast partial sorting of an array on a rank subinterval
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Copyright 2025 Igor Burago. Released under the ISC License. | |
| #include <limits.h> // CHAR_BIT | |
| #include <stddef.h> // ptrdiff_t | |
| #include <stdint.h> | |
| #include <string.h> // memcpy(), memmove(), memset() | |
| // Built-in u128 is not strictly required, but it makes it easier to guarantee | |
| // the absence of overflows during sampling in rank_partition() for all possible | |
| // input array lengths. It also simplifies the implementation of the mcg64 RNG. |