jonnifyfsharp

Module C4.03

Sorting & searching

Order is a debt you pay once. Pay it well, and every later lookup is cheap forever after.

Sorting and searching are two halves of one bargain. Put a sequence in order once — at a cost of about n log n comparisons — and every later lookup drops from an O(n) scan to an O(log n) binary search. The two best comparison sorts, merge sort and quicksort, are the divide-and-conquer recursion of C4.02 applied to a list; binary search is that same halving over a sorted sequence. This module re-derives all three in F#, at parity with the Elixir course's F4.03, and notes where the CLR's cost model differs from the BEAM's. The tie that runs through every dive is the F# EchoMQ: its pending jobs live in a Set sorted by branded id, so byte order is mint order and a claim is a pop-minimum, never a re-sort.

The three dives Back to C4 · Algorithms & Data Structures

Order, once — then halve

An unordered sequence answers "is 20 in here?" only by checking every element. A sorted sequence answers it by halving: look at the middle, then the half that could contain the target. The first cost is the sort; the standing benefit is every search after it. Select an angle to see the sort, the search, and the cost over the running sequence — the same one the Elixir course uses, computed here by real F#.

The running sequence is [12; 8; 30; 5; 10; 20; 42] unsorted, which List.sort turns into [5; 8; 10; 12; 20; 30; 42]. Every readout below is the actual output of the named F# expression, verified in dotnet fsi.

The angle · select one

5 0 8 1 10 2 12 3 20 4 30 5 42 6 List.sort [12; 8; 30; 5; 10; 20; 42] 

      

      
role: rearrange into order

      
result: [5; 8; 10; 12; 20; 30; 42]

    

    
Sorting is work you do once so that searching is cheap forever after. The rest of the module is how
      each half is built in F# — and why the price of sorting cannot drop below n log n for a
      comparison sort.

  


  
  

    
Where the bus meets this module

    

      
The bus this chapter grounds in is echo_fs — the F# port of the Valkey-native EchoMQ
        queue (the in-memory core is built and tested; the Valkey transport is coming soon). One design choice ties it
        to sorting and searching at once. Each queue keeps its waiting jobs not as a list but as a
        Set<string> of branded ids, and an F# Set is an ordered,
        balanced-tree structure: it holds its elements sorted and answers membership in O(log n).

      
Because a branded id encodes its mint time in the high bits and is written in fixed-width Base62, a later mint
        is always a larger string — so the Set's natural order is arrival order. The
        store comment states it directly: "the id order IS the mint order — the 'no second index' property." Nothing
        has to be re-sorted; the oldest job is the minimum of the set. That single fact reappears in all three dives.

    


    

      
EchoMQ in F#

      
The pending set, in one quote

      
This is the field declaration and the claim path of the real EchoMQ.Store module,
        quoted from echo_fs/EchoMQ/Store.fs. Pending is a
        Set; a claim pops its minimum element — the oldest job — and the set re-balances around
        the gap. There is no separate ordering index to keep in step.

      
// echo_fs/EchoMQ/Store.fs — the queue state
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>        // ids, kept in mint order by Set
      // Schedule, Active, Dead, … omitted }

// claim the oldest pending job: pop the minimum id (mint order)
let id = Set.minElement st.Pending


      
Status. The in-memory Store does this today, and the
        EchoMQ.Tests suite covers it. The Valkey transport
        (EchoMQ.Connector) — which keeps the same order in a sorted set on the server — lands
        next.

    

    
A queue is a sorting problem hiding in a data structure: keep ids in mint order, and "the next job"
      is the minimum, "browse the backlog" is the reverse, and "find what is due" is a range query. The three dives
      take each in turn.

  


  
  

    
The three dives

    

      
Read them in order. Each stands on valid F#: every result shown was produced by dotnet fsi,
        and every EchoMQ in F# block quotes the real echo_fs source. Together they take
        a sort from n log n down to a single search, and show how the bus leans on order to
        serve, browse, and schedule its jobs.

    

    

      live module hub
      built dive ready
      soon specified
    

    

      

        
          
C4.03.1built

          
Merge sort

          
Halve positionally, sort each half, merge — a stable O(n log n) sort over immutable lists, the property the pending set leans on.

          
  • mergethe work is in the merge; equal keys keep their order

        
        
          
C4.03.2built

          
Quicksort

          
Partition the rest around a pivot, recurse, concatenate — the cost is the partition, and immutability changes what each split copies.

          
  • quickpartitioning, immutability, and comparison cost

        
        
          
C4.03.3built

          
Searching

          
O(n) linear over any sequence, O(log n) binary over a sorted array — and the same O(log n) in a Set or Map, the way the bus finds a job by id and by due time.

          
  • searchlinear, binary, and the log-n lookup of a Set / Map

        
      

    

  


  
  

    
The F# cost model, against the BEAM

    

      
The algorithms are the same on both runtimes; the cost model is not, on two points. First, both
        F#'s list and Elixir's list are singly-linked cons cells, so a list has no O(1) random
        access — binary search wants an array (an indexable CLR array), exactly as the Elixir
        version wants a tuple. Second, F#'s List.sort and Array.sort
        are stable, the same guarantee Elixir's Enum.sort gives, and for the
        same reason: a stable merge keeps equal elements in their original order.

      
Where the CLR differs is the comparison itself. F# is statically typed, so a sort over
        int or string compiles to a direct structural comparison with
        no per-element dispatch; the BEAM compares terms at run time. And an F# Set or
        Map is a balanced tree giving O(log n) lookup with structural sharing — the same Big-O
        as a balanced tree on the BEAM, the topic the next module turns to in full.

    

    

      

        
Elixir / F4.03 · sort a flat sequence, then halve it

        
Merge sort and quicksort over a list; binary search wants a tuple, where elem/2 is O(1).

      

      
      

        
F# / C4.03 · the same arc, statically typed

        
The same two sorts over list; binary search wants an array; a Set gives ordered O(log n) lookup, and the bus is built on it.

      

    

    
Start with merge sort, then
      quicksort, then
      searching. Next module: C4.04 — Maps, sets &
      hashing, where a hash trades ordering for average-O(1) lookup.

  


  
  

    
Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

    
References

    

      

        
Sources

        
      

      

        
Related in this course