Before you can find anything
you have to sort everything.

// Use the standard library. Always.
// It is faster than anything you would write.

fn stdlib_sorting_examples() {
    let mut nums = vec![5, 3, 8, 1, 4, 2, 7, 6];

    // Stable sort (Timsort) -- equal elements keep original order
    nums.sort();
    // [1, 2, 3, 4, 5, 6, 7, 8]

    // Unstable sort (pdqsort) -- faster, same O(n log n) guarantee
    nums.sort_unstable();
    // same result here, but equal elements may reorder

    // Custom comparator
    let mut words = vec!["banana", "apple", "cherry", "date"];
    words.sort_by(|a, b| a.len().cmp(&b.len()));
    // ["date", "apple", "banana", "cherry"]

    // Sorting Bitcoin mempool transactions by fee rate (descending)
    #[derive(Debug)]
    struct MempoolEntry { fee_rate: u64, size_vbytes: u32 }

    let mut mempool = vec![
        MempoolEntry { fee_rate: 100, size_vbytes: 250 },
        MempoolEntry { fee_rate: 500, size_vbytes: 141 },
        MempoolEntry { fee_rate: 250, size_vbytes: 300 },
    ];
    // highest fee rate mines first -- pdqsort, O(n log n) worst case
    mempool.sort_unstable_by(|a, b| b.fee_rate.cmp(&a.fee_rate));
    // [{500, 141}, {250, 300}, {100, 250}]

    // sort_by_key for cleaner field extraction
    mempool.sort_unstable_by_key(|tx| std::cmp::Reverse(tx.fee_rate));
}

#include <stdlib.h>
#include <stdint.h>
#include <string.h>

/* qsort() comparison functions.
 * void* args are untyped -- no compile-time safety. */

int cmp_int_asc(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    /* never use return x - y: integer overflow is undefined */
    return (x > y) - (x < y);
}

int cmp_int_desc(const void *a, const void *b) {
    return cmp_int_asc(b, a);
}

/* Bitcoin mempool: sort by fee rate descending */
typedef struct {
    uint64_t fee_rate;    /* satoshis per virtual byte */
    uint32_t size_vbytes;
    uint8_t  txid[32];
} MempoolEntry;

static int cmp_fee_desc(const void *a, const void *b) {
    const MempoolEntry *ea = a;
    const MempoolEntry *eb = b;
    if (eb->fee_rate > ea->fee_rate) return  1;
    if (eb->fee_rate < ea->fee_rate) return -1;
    return 0;
}

void sort_mempool(MempoolEntry *pool, size_t n) {
    /* O(n log n) average, O(n^2) worst case in some impls */
    qsort(pool, n, sizeof *pool, cmp_fee_desc);
}

int main(void) {
    int nums[] = {5, 3, 8, 1, 4};
    qsort(nums, 5, sizeof *nums, cmp_int_asc);
    /* [1, 3, 4, 5, 8] */

    MempoolEntry pool[] = {
        {100, 250, {0}},
        {500, 141, {0}},
        {250, 300, {0}},
    };
    sort_mempool(pool, 3);
    /* [{500,...}, {250,...}, {100,...}] -- highest fee first */
    return 0;
}

use std::cmp::Reverse;

#[derive(Debug, Eq, PartialEq)]
struct MempoolEntry {
    fee_rate:    u64,      // satoshis per virtual byte
    size_vbytes: u32,      // transaction weight
    txid:        [u8; 32], // transaction identifier
}

impl Ord for MempoolEntry {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // descending fee rate: highest mines first
        other.fee_rate.cmp(&self.fee_rate)
    }
}

impl PartialOrd for MempoolEntry {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn build_block<'a>(
    mempool: &'a mut Vec<MempoolEntry>,
    block_limit_vbytes: u32,
) -> Vec<&'a MempoolEntry> {
    // O(n log n) -- pdqsort via sort_unstable()
    mempool.sort_unstable();

    let mut block = Vec::new();
    let mut used  = 0u32;

    for entry in mempool.iter() {
        if used + entry.size_vbytes > block_limit_vbytes { break; }
        block.push(entry);
        used += entry.size_vbytes;
    }
    block
    // This is the algorithm that decides
    // whose Bitcoin transaction confirms next
    // and whose waits another ten minutes.
    // A sort on an array.
    // The most consequential sort in finance.
}

#include <stdint.h>
#include <stdlib.h>
#include <stddef.h>

typedef struct {
    uint64_t fee_rate;     /* sat / vbyte */
    uint32_t size_vbytes;
    uint8_t  txid[32];
} MempoolEntry;

/* highest fee rate first */
static int cmp_fee_rate(const void *a, const void *b) {
    const MempoolEntry *ea = a;
    const MempoolEntry *eb = b;
    if (eb->fee_rate > ea->fee_rate) return  1;
    if (eb->fee_rate < ea->fee_rate) return -1;
    return 0;
}

/* returns number of selected transactions */
size_t build_block(MempoolEntry *pool, size_t n,
                   uint32_t block_limit,
                   size_t   *selected_idx) {
    /* O(n log n) sort by fee rate descending */
    qsort(pool, n, sizeof *pool, cmp_fee_rate);

    uint32_t used  = 0;
    size_t   count = 0;

    for (size_t i = 0; i < n; i++) {
        if (used + pool[i].size_vbytes > block_limit) break;
        selected_idx[count++] = i;
        used += pool[i].size_vbytes;
    }
    return count;
}
/* Sorting decides financial priority.
 * The algorithm is O(n log n).
 * The stakes are measured in satoshis. */