borisd
— Software Developer

Order matching: algorithms [1] (draft)

Published at: July 20, 2025 Lang: en

I stumbled upon my bachelor thesis, where i made a trading system for virtual 'coins' at work. And i remembered how i tried to research and write up on order matching algorithms, but had no time for that. Now i have, and i'm starting...

Introduction

Basically, the idea of trading is - I have stock to sell (as expensive as possible), you have money and the desire to buy (as cheap as possible). Trading systems make it possible, fair and efficient, using 'orders'.
These orders are stored in an 'order book', which maintains the current state of the market by organizing all active buy and sell orders. A Depth of Market (DoM) view represents this order book, typically showing aggregated volumes at each price level (red/green tables).

Order book — A data structure that maintains a sorted collection of all active, unfilled limit orders for a particular financial instrument,

Order matching — The process of matching buy and sell orders in a trading system, ensuring that trades are executed when prices align.

And specifically for this aritcle:

Price-Time Priority (First-In-First-Out) — Orders are matched based on the best price, and among orders at the same price, the earliest one is executed first.

Let's define the simplest "Order" data structure:

Order

Field	Type	Description
side	bool	true for buy (bid), false for sell (ask)
price	int	price in 'cents'
quantity	int	quantity of a good
sequence	int	instead of a timestamp, an increasing sequence number

For example, if we have the following orders:

{side: true, price: 100, quantity: 1, sequence: 0}

{side: false, price: 100, quantity: 1, sequence: 1}

They are going to be matched and executed: the quantity of one will be reduced from both orders. Before execution, order book (or its DoM) can look like this:

Price	Amount
100	1
100	1

After - it's going to be empty.

So, in reality, the price level, where bid and ask meet (market price) is invisible, as orders are executed immediately there.
For example, if we have the following order book, see what happens when you place a new order (push buttons):

Price	Amount
103	1
102	1
101	1
100	1
99	1
98	1

Algorithms and Data Structures / naive

So, how do we match orders? Or how do we maintain the order book? We can start with a discussion of data structures.

Operations we need:

Add (place) an order
Update an order
Remove an order
Look up / find: to match the orders, we need the most cheap ask and the most expensive bid

Let's start with ADTs for just storing orders first:

Suitable Abstract Data Types:

List: the most intuitive
Map: what else supports updates and deletions

TODO: Algorithms / for a scale

So, if we have millions of orders per second, how do we match them?

borisd— Software Developer