Most efficient know way to match orders

Consider two 2D-Array $B_{ij} $ (the buy array) and $S_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in turn, is associated with an array of integers.

For example

B = [ 
  0001 => [ 32.5 => {10, 15, 20}, 
            45.2 => {48, 16, 19}, 
            ...,
            k1
          ], 
  0002 => [ 35.6 => {17, 35, 89}, 
            68.7 => {18, 43, 74}, 
            ...,
            k2
          ] 
]

and similiarly for the sell array.

This is akin to an order association system of a stock/commodity exchange

BuyOrderBook = [
                 CompanyName => [
                                 Price1 => [Qty1, Qty2...],
                                 Price2 => [Qty1, Qty2...]
                                ]
                 SecondCompany = [...]
               ]

What is the fastest way known to solve the following problem:


Input: Buy array $B$, Sell array $S$

Problem: Decide wether there are $(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$ and $(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$ with $q_1, q_2 > 0$ and $p_2 \geq p_1$.

In short, what is the fatest way of matching orders for an exchange?

Update in response to comments

Lets say, MSFT has 25 shares @ \$60 to be sold and there is buyer who is willing to offer \$61 for 10 shares of MSFT. Then the buyer gets 10 shares @ \$60 and the buy order book becomes empty while the sell order book now is updated with new quantity - 15 shares @ \$60.

Now take the reverse case, MSFT has 25 shares @ \$60 to be bought and there is seller who is willing to receive \$61 for 10 shares of MSFT. Then the trade will not be executed because seller is demanding a minimum of \$61 and the buyer is offering a maximum of \$60. The orders are now stored and await until new orders are received.

(This is the limit order principle, where the seller specifies minimum price at which he is willing to sell at and buyer spe

Maintain your buy-order book as an array of companies.
For each company, keep a priority queue of prices (max for buy and min for sell).
For each price, keep a queue of orders.

To check for matching orders, for each company, call find-min() and find-max() on the company in the sell array and buy array to find the best buy/sell prices. If max > min, then try to fulfill the order. To fulfill the order, pull elements off of your buy and sell queues for that company and price, until one of your price queues is empty. When the price queue is empty, delete the corresponding element from its priority queue, and perform the check again.

This strategy costs constant time per order, and $O(\log p_i)$ per price change, where $p_i$ is the number of prices for company $i$.

StackExchange Computer Science Q#1004, answer score: 5