How are txns sorted correctly in Merkle trees between nodes and validated via Proof of Work
But the merkle root must be different to each miner/node due to transaction order and the generation transaction,

Correct.

so how do other nodes come to consensus if their transactions are different.

They don't. Every miner is fully responsible for the choice of their own transactions. There is no need for different miners to agree on the transaction selection. The winning miner decides the contents of the winning block, and other go along with it, accepting their transaction selection (unless the included transactions are objectively invalid, which makes the block invalid - to miners and other nodes).

I imagine they would use the nonce provided by the block creator to hash their own copy of the block and see if it in within the target.

There are many block validity rules that are performed by all nodes, including the verification of proof-of-work, like you say. Other rules include verifying that all transactions are valid, that no theft occurred, that no double spending occurred, that no money is printed by the block (beyond the permitted subsidy), ...

Wouldnt the tree have to be hashed again

Yes.
There are a number of layers involved to updating a miner's candidate block. Each is much faster than the previous one, but done much more often:

Typically the mining software will occasionally (say, every few seconds) build a new block template to work on, which includes transaction selection.

An intermediate layer changes the coinbase transaction (which includes payout address, as well as an &quot;extra nonce&quot;) every so often. Every time this happens the Merkle root changed. However, by caching the inner nodes of the Merkle tree that are just right of the leftmost branch in the tree, this is just O(log(n)) work in the number of transactions (e.g. a block with 2048 transactions only needs 11 hashing steps to recompute the Merkle root).

The lowest-level hardware layer cycles through the 232 nonces in the block header, all with the same Merkle root. This is extremely efficient.



and the PoW would have to start from the beginning.

Yes, but this is irrelevant. PoW doesn't have &quot;progress&quot;. You don't lose anything by starting over, as long as you're still trying hashes all the time. Every candidate block you try (combination of tx selection, coinbase tx, nonce) has an independent chance of meeting the PoW target (a chance equal to 2256 / target). If that chance is 1/c, and you perform h hashes per day, you will find h/c block per day - regardless of which transactions those attempts are for.