From 77f1c55974df0e3e9f088eb8972dae83cbae70cc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Sat, 31 Jul 2021 22:58:39 +0200 Subject: inner_sort_by: comments --- cli/src/main.rs | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'cli/src/main.rs') diff --git a/cli/src/main.rs b/cli/src/main.rs index e405e48..3ffbe88 100644 --- a/cli/src/main.rs +++ b/cli/src/main.rs @@ -161,15 +161,16 @@ fn inner_sort_by(v: &mut [T], cmps: &mut [F]) where F: FnMut(&T, &T) -> Ordering, { - // Early out - if v.len() < 2 || cmps.is_empty() { + if v.is_empty() || cmps.is_empty() { return; } + // Sort the slice using the first comparison. v.sort_by(&mut cmps[0]); + // Find ranges of consecutive equal items according to the first comparison. let mut ranges = Vec::new(); - let mut lower = 0; // Lower bound of current equal range + let mut lower = 0; // Lower bound of current equal range. for i in 0..v.len() { if cmps[0](&v[i], &v[lower]) != Ordering::Equal { ranges.push(lower..i); @@ -177,6 +178,8 @@ where } } + // If we still have comparisons to use, sort the ranges of consecutive items recursively. + // The recursion ensures that ranges of equal items aren't mixed between comparisons further down. if cmps.len() != 1 { for range in ranges { inner_sort_by(&mut v[range], &mut cmps[1..]); -- cgit v1.2.1