Efficient streaming sort

Question

Consider following task:

we have an input of N+1 lines, where first line contains N ≤ 150000 - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id ≤ 10^7, m ≤ 100.
We have to perform a stable sort on this sequence and print the result.

Sample input:

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

Sample output:

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

My current naive implementation was just allocate vector of size N, fill it, and then run any stable sort algorithm on it. In following example (all examples are written in Rust) I'm just adding row number as part of the sorting key and then perform quick sort:

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);
    }
}

My second implementation used BTreeSet, but it wasn't a success, and it have taken much more time than first naive one.

My third idea was using idea from insertion sort to keep array sorted from the scratch. When we get yet another element from the stream we just seek the position where it should be placed and then insert in there. When all elements are processed we already have a final array. Here is a sample implementation:

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
}

However, it was even slower than a BTree one and it timed out.

I wonder what are theoretical and practical optimal implementations?
I mean I think that in theory BTree should be faster on this task, but in practice simple array sort beats it.

Answer 1

First, it should not be surprising that if you want to sort some numbers, a dedicated sorting algorithm is faster than using a data structure that is capable of sorting and also doing other things (finding given elements efficiently, inserting new elements efficiently, removing elements efficiently). (That said, you should find that the difference is "only" a constant factor, at least for sufficiently large inputs.)

Since the maximum m value is very small, you can just use a slight variant of counting sort, which takes $O(n+m)$ time and memory. Declare an array freq[] of size 101, then in a first pass through all the numbers, increment the corresponding element of freq for each number: this is to decide the bucket sizes. Then allocate a fresh length-$n$ buffer output[], and make a pass through the 101 elements of freq, changing each element to the total so far: after doing this, freq[i] conceptually points to one past the end position of a block within output[] that is large enough to hold all input numbers having key equal to i. Now make a final pass in reverse order through the n input elements, writing each to the next free space available within its block and decrementing the position accordingly. (Literally for (int i = n - 1; i >= 0; --i) output[--freq[input[i].m] = input[i].id; in C++.)

There are no truly "streaming" sorting algorithms, since the very last number read could be smaller than all the others, meaning you have to either buffer them, or save partial results to disk.

Answer 2

Here is an algorithm to consider https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8982863/