diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -852,6 +852,11 @@
     indexed_disconnected_transactions queuedTx;
     uint64_t cachedInnerUsage = 0;
 
+    void addTransaction(const CTransactionRef &tx) {
+        queuedTx.insert(tx);
+        cachedInnerUsage += RecursiveDynamicUsage(tx);
+    }
+
 public:
     // It's almost certainly a logic bug if we don't clear out queuedTx before
     // destruction, as we add to it while disconnecting blocks, and then we
@@ -872,15 +877,14 @@
                cachedInnerUsage;
     }
 
+    const indexed_disconnected_transactions &GetQueuedTx() const {
+        return queuedTx;
+    }
+
     // Add entries for a block while reconstructing the topological ordering so
     // they can be added back to the mempool simply.
     void addForBlock(const std::vector<CTransactionRef> &vtx);
 
-    void addTransaction(const CTransactionRef &tx) {
-        queuedTx.insert(tx);
-        cachedInnerUsage += RecursiveDynamicUsage(tx);
-    }
-
     // Remove entries based on txid_index, and update memory usage.
     void removeForBlock(const std::vector<CTransactionRef> &vtx) {
         // Short-circuit in the common case of a block being added to the tip
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -156,6 +156,7 @@
         if (it == mapTx.end()) {
             continue;
         }
+
         auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
         // First calculate the children, and update setMemPoolChildren to
         // include them, and update their setMemPoolParents to include this tx.
@@ -635,8 +636,13 @@
 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef> &vtx,
                                 unsigned int nBlockHeight) {
     LOCK(cs);
+
+    DisconnectedBlockTransactions disconnectpool;
+    disconnectpool.addForBlock(vtx);
+
     std::vector<const CTxMemPoolEntry *> entries;
-    for (const auto &tx : vtx) {
+    for (const CTransactionRef &tx : boost::adaptors::reverse(
+             disconnectpool.GetQueuedTx().get<insertion_order>())) {
         uint256 txid = tx->GetId();
 
         indexed_transaction_set::iterator i = mapTx.find(txid);
@@ -648,7 +654,8 @@
     // Before the txs in the new block have been removed from the mempool,
     // update policy estimates
     minerPolicyEstimator->processBlock(nBlockHeight, entries);
-    for (const auto &tx : vtx) {
+    for (const CTransactionRef &tx : boost::adaptors::reverse(
+             disconnectpool.GetQueuedTx().get<insertion_order>())) {
         txiter it = mapTx.find(tx->GetId());
         if (it != mapTx.end()) {
             setEntries stage;
@@ -659,6 +666,8 @@
         ClearPrioritisation(tx->GetId());
     }
 
+    disconnectpool.clear();
+
     lastRollingFeeUpdate = GetTime();
     blockSinceLastRollingFeeBump = true;
 }
@@ -1270,7 +1279,7 @@
 
 void DisconnectedBlockTransactions::addForBlock(
     const std::vector<CTransactionRef> &vtx) {
-    for (const auto &tx : vtx | boost::adaptors::sliced(1, vtx.size())) {
+    for (const auto &tx : vtx) {
         // If we already added it, just skip.
         auto it = queuedTx.find(tx->GetId());
         if (it != queuedTx.end()) {
@@ -1290,8 +1299,9 @@
         // if we already know of the parent of the current transaction. If so,
         // we remove them from the set and then add them back.
         while (parents.size() > 0) {
-            std::unordered_set<TxId, SaltedTxidHasher> worklist =
-                std::move(parents);
+            std::unordered_set<TxId, SaltedTxidHasher> worklist(
+                std::move(parents));
+
             for (const TxId &txid : worklist) {
                 // If we do not have that txid in the set, nothing needs to be
                 // done.
@@ -1328,6 +1338,7 @@
                                                           bool fAddToMempool) {
     AssertLockHeld(cs_main);
     std::vector<uint256> vHashUpdate;
+
     // disconnectpool's insertion_order index sorts the entries from oldest to
     // newest, but the oldest entry will be the last tx from the latest mined
     // block that was disconnected.
@@ -1362,6 +1373,7 @@
     // We also need to remove any now-immature transactions
     mempool.removeForReorg(config, pcoinsTip, chainActive.Tip()->nHeight + 1,
                            STANDARD_LOCKTIME_VERIFY_FLAGS);
+
     // Re-limit mempool size, in case we added any transactions
     mempool.LimitSize(
         gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000,
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -2891,6 +2891,7 @@
         // any disconnected transactions back to the mempool.
         disconnectpool.updateMempoolForReorg(config, true);
     }
+
     mempool.check(pcoinsTip);
 
     // Callbacks/notifications for a new best chain.
diff --git a/test/functional/abc-transaction-ordering.py b/test/functional/abc-transaction-ordering.py
--- a/test/functional/abc-transaction-ordering.py
+++ b/test/functional/abc-transaction-ordering.py
@@ -92,8 +92,8 @@
                     spendable_outputs.append(PreviousSpendableOutput(tx, i))
                 # Put some random data into the transaction in order to randomize ids.
                 # This also ensures that transaction are larger than 100 bytes.
-                tx.vout.append(
-                    CTxOut(0, CScript([random.getrandbits(256), OP_RETURN])))
+                rand = random.getrandbits(256)
+                tx.vout.append(CTxOut(0, CScript([rand, OP_RETURN])))
                 return tx
 
             tx = get_base_transaction()