diff --git a/rust/hg-core/src/dirstate_tree/dirstate_map.rs b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
--- a/rust/hg-core/src/dirstate_tree/dirstate_map.rs
+++ b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
@@ -45,10 +45,11 @@
 /// Using a plain `HgPathBuf` of the full path from the repository root as a
 /// map key would also work: all paths in a given map have the same parent
 /// path, so comparing full paths gives the same result as comparing base
-/// names. However `BTreeMap` would waste time always re-comparing the same
+/// names. However `HashMap` would waste time always re-hashing the same
 /// string prefix.
+pub(super) type NodeKey<'on_disk> = WithBasename<Cow<'on_disk, HgPath>>;
 pub(super) type ChildNodes<'on_disk> =
-    FastHashMap<WithBasename<Cow<'on_disk, HgPath>>, Node<'on_disk>>;
+    FastHashMap<NodeKey<'on_disk>, Node<'on_disk>>;
 
 /// Represents a file or a directory
 #[derive(Default)]
@@ -64,10 +65,20 @@
     tracked_descendants_count: usize,
 }
 
-impl Node<'_> {
+impl<'on_disk> Node<'on_disk> {
     pub(super) fn state(&self) -> Option<EntryState> {
         self.entry.as_ref().map(|entry| entry.state)
     }
+
+    pub(super) fn sorted<'tree>(
+        nodes: &'tree mut ChildNodes<'on_disk>,
+    ) -> Vec<(&'tree NodeKey<'on_disk>, &'tree mut Self)> {
+        let mut vec: Vec<_> = nodes.iter_mut().collect();
+        // `sort_unstable_by_key` doesn’t allow keys borrowing from the value:
+        // https://github.com/rust-lang/rust/issues/34162
+        vec.sort_unstable_by(|(path1, _), (path2, _)| path1.cmp(path2));
+        vec
+    }
 }
 
 /// `(full_path, entry, copy_source)`
diff --git a/rust/hg-core/src/dirstate_tree/status.rs b/rust/hg-core/src/dirstate_tree/status.rs
--- a/rust/hg-core/src/dirstate_tree/status.rs
+++ b/rust/hg-core/src/dirstate_tree/status.rs
@@ -110,11 +110,9 @@
 
         // `merge_join_by` requires both its input iterators to be sorted:
 
-        let mut dirstate_nodes: Vec<_> = dirstate_nodes.iter_mut().collect();
+        let dirstate_nodes = Node::sorted(dirstate_nodes);
         // `sort_unstable_by_key` doesn’t allow keys borrowing from the value:
         // https://github.com/rust-lang/rust/issues/34162
-        dirstate_nodes
-            .sort_unstable_by(|(path1, _), (path2, _)| path1.cmp(path2));
         fs_entries.sort_unstable_by(|e1, e2| e1.base_name.cmp(&e2.base_name));
 
         itertools::merge_join_by(