[messaging] InMemoryStore sorts on every insert — O(n log n) per message

[intendednull]

Parent: #108

Problem

crates/messaging/src/store.rs:88-110:

fn insert(&mut self, message: Message) -> Result<(), StoreError> {
    // ...
    self.messages.insert(id.clone(), message);
    let ids = self.channel_index.entry(channel_id).or_default();
    ids.push(id);

    // Keep the channel index sorted by HLC timestamp.
    ids.sort_by(|a, b| {
        let ma = &self.messages[a];
        let mb = &self.messages[b];
        ma.hlc.cmp(&mb.hlc)
    });
    // ...
}

Every insert runs a full sort_by over the channel's message list. For a channel with N messages, each insert is O(N log N) — inserting N messages is O(N² log N) total. At 1000 messages per channel this is painful; CLAUDE.md's scaling tests include message floods that this will degrade on.

Fix

Replace the Vec<MessageId> channel index with an ordered structure, or keep the Vec and use binary insert:

Option A (smallest change): binary insert. Vec::binary_search_by + insert gives O(log N) search and O(N) insert.

let pos = ids.binary_search_by(|existing| {
    self.messages[existing].hlc.cmp(&new_hlc)
}).unwrap_or_else(|e| e);
ids.insert(pos, id);

Option B (cleaner): use BTreeMap<HlcTimestamp, Vec<MessageId>>. Deterministic, sorted iteration, and handles duplicate HLC timestamps gracefully.

Recommend option B for ergonomics.

Test

Benchmark / regression test:

#[test]
fn insert_1000_messages_is_linear() {
    let mut store = InMemoryStore::new();
    let start = Instant::now();
    for i in 0..1000 {
        let msg = test_message_with_hlc(i);
        store.insert(msg).unwrap();
    }
    let elapsed = start.elapsed();
    // Previously O(N² log N) — should now fit comfortably
    assert!(elapsed < Duration::from_millis(100));
}

Also verify listing still returns messages in HLC order after random-order insertion.

[intendednull]

Already implemented in commit 8f8a125 (merged via #146): replaced the O(N log N) sort-on-every-insert with a BTreeMap<HlcTimestamp, Vec<MessageId>> channel index in crates/messaging/src/store.rs. Closing as resolved.