Sort de streaming efficace

Question

Considérez la tâche suivante: nous avons une entrée de n + 1 lignes, où la première ligne contient n - nombre d'éléments, puis nous avons n lignes, chacune contient un élément, qui est un tuple (ID numéro, numéro m), ID <10 ^ 9, m <100. Nous devons effectuer un type stable sur cette séquence et imprimer le résultat.

Exemple d'entrée:

8
1 2
16 3
11 2
20 3
3 5
26 4
7 1
22 4

Exemple de sortie:

3 5
26 4
22 4
16 3
20 3
1 2
11 2
7 1

Mon implémentation naïve actuelle allait simplement allouer le vecteur de la taille n, le remplir, puis exécuter n'importe quel alhorithme de tri stable. Dans l'exemple suivant (tous les exemples sont écrits en rouille), j'ajoute simplement le numéro de ligne dans le cadre de la touche de tri, puis effectuez un tri rapide:

use std::io::{self, BufRead};
use std::cmp::Ordering;

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();
        tuples.push((id, m, i));
    }

    tuples.sort_unstable_by(|a, b| {
        let cmp = b.1.cmp(&a.1);
        match cmp {
            Ordering::Equal => a.2.cmp(&b.2),
            other => other
        }
    });

    for (id, m, ..) in tuples {
       println!("{} {}", id, m);
    }
}

Ma deuxième implémentation utilisée BTreeSet, mais ce n'était pas un succès, et cela a pris beaucoup plus de temps que le premier naïf.

Ma troisième idée a été d'utiliser l'idée de l'insertion pour garder le tableau trié à partir de zéro. Lorsque nous obtenons un autre élément du flux, nous recherchons simplement la position où elle doit être placée, puis y insérez. Lorsque tous les éléments sont traités, nous avons déjà un tableau final. Voici un exemple de mise en œuvre:

use std::io::{self, BufRead};
use std::cmp::Ordering;

struct TeamResult {
    id: u32,
    m: u8,
}

impl TeamResult {
    pub fn new(id: u32, m: u8) -> Self {
        Self {
            id,
            m
        }
    }
}

impl Ord for TeamResult {
    fn cmp(&self, other: &Self) -> Ordering {
        other.m.cmp(&self.m)
    }
}

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

impl PartialEq for TeamResult {
    fn eq(&self, other: &Self) -> bool {
        self.m.eq(&other.m)
    }
}

impl Eq for TeamResult { }

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();

        let item_to_insert = TeamResult::new(id, m);
        let index_to_insert = search_pos(&tuples[0..i], &item_to_insert);
        tuples.insert(index_to_insert, item_to_insert);
    }

    for x in tuples {
        println!("{} {}", x.id, x.m);
    }
}

fn search_pos<T: Ord>(a: &[T], value: &T) -> usize {
    let len = a.len();

    if len == 0 {
        return 0;
    }

    if value < &a[0] {
        return 0;
    }

    if value > &a[len - 1] {
        return len;
    }

    let mut lo = 0;
    let mut hi = len - 1;

    while lo < hi {
        let mid = (hi + lo) / 2;

        match value.cmp(&a[mid]) {
            Ordering::Less => hi = mid - 1,
            Ordering::Greater => lo = mid + 1,
            Ordering::Equal => {
                lo = mid;
                break;
            }
        };
    }

    while lo <= hi && value >= &a[lo] {
        lo += 1
    }

    lo
}

Cependant, il était encore plus lent qu'un btree et il était éloigné.

Je me demande quelles sont les implémentations optimales théoriques et pratiques? Je veux dire que je pense qu'en théorie, Btree devrait être plus rapide sur cette tâche, mais en pratique, un simple tableau le bat le bat.