How does mining software choose transactions from a memory pool to include them in a block? Does mining software just include transactions in order each time it receives them? Or they choose transactions which has higher fees?
This is really an implementation detail and every miner could operate on a wide variety of mining strategies. That being said, AFAIK miner miners/pools run the standard algorithm included in Geth, which is:
- Discard anything below a threshold
- Gather all the executable transactions (i.e. one for each account)
- Pick the more expensive one
- Repeat from step 2. until no more transactions fit into the block
- The algorithm is actually a bit smarter and does a fancy sort so that steps 2-3-4 can be done simply by iterating over a specially sorted array.
- Checking whether a transaction fits into a block or not uses the stated gas limit of the transaction, not the actual consumption (since the latter would require actually running the transaction first, which we don't want to).
- Based on the above, if the block is almost full, it can easily happen that a lower priced transaction gets included over a higher priced one if the higher one doesn't fit but the lower one does.