RustPython · kangdora · Jul 31, 2026 · Jul 31, 2026 · Jul 31, 2026 · Jul 31, 2026
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
@@ -305,7 +305,6 @@ textwrap = { version = "0.16.2", default-features = false }
 termios = "0.3.3"
 thiserror = "2.0"
 thin-vec = "0.2.14"
-timsort = "0.1.2"
 tk-sys = { git = "https://github.com/arihant2math/tkinter.git", tag = "v0.2.0" }
 icu_casemap = "2"
 icu_locale = "2"

diff --git a/crates/vm/Cargo.toml b/crates/vm/Cargo.toml
@@ -80,7 +80,6 @@ half = { workspace = true }
 psm = { workspace = true }
 optional = { workspace = true }
 result-like = { workspace = true }
-timsort = { workspace = true }
 
 [target.'cfg(unix)'.dependencies]
 exitcode = { workspace = true }

diff --git a/crates/vm/src/builtins/list.rs b/crates/vm/src/builtins/list.rs
@@ -9,18 +9,19 @@ use crate::common::lock::{
 use crate::object::{Traverse, TraverseFn};
 use crate::{
     AsObject, Context, Py, PyObject, PyObjectRef, PyPayload, PyRef, PyResult,
-    builtins::PyStr,
+    builtins::{PyFloat, PyInt, PyStr, PyTuple},
     class::PyClassImpl,
     convert::ToPyObject,
-    function::{ArgSize, FuncArgs, OptionalArg, PyComparisonValue},
+    function::{ArgSize, Either, FuncArgs, OptionalArg, PyComparisonValue},
     iter::PyExactSizeIterator,
     protocol::{PyIterReturn, PyMappingMethods, PySequenceMethods},
     recursion::ReprGuard,
     sequence::{MutObjectSequenceOp, OptionalRangeArgs, SequenceExt, SequenceMutExt},
     sliceable::{SequenceIndex, SliceableSequenceMutOp, SliceableSequenceOp},
+    sorting::timsort,
     types::{
         AsMapping, AsSequence, Comparable, Constructor, Initializer, IterNext, Iterable,
-        PyComparisonOp, Representable, SelfIter,
+        PyComparisonOp, Representable, RichCompareFunc, SelfIter,
     },
     vm::VirtualMachine,
 };
@@ -634,33 +635,250 @@ impl Representable for PyList {
     }
 }
 
+enum Elem {
+    Str,
+    Int,
+    Float,
+    Object(RichCompareFunc),
+    Generic,
+}
+
+enum PreSort {
+    Str,
+    Int,
+    Float,
+    Object(RichCompareFunc),
+    Tuple(Elem),
+    Generic,
+}
+
+impl From<Elem> for PreSort {
+    fn from(e: Elem) -> Self {
+        match e {
+            Elem::Str => Self::Str,
+            Elem::Int => Self::Int,
+            Elem::Float => Self::Float,
+            Elem::Object(f) => Self::Object(f),
+            Elem::Generic => Self::Generic,
+        }
+    }
+}
+
+fn classify(class: &Py<PyType>, vm: &VirtualMachine) -> Elem {
+    if class.is(vm.ctx.types.str_type) {
+        Elem::Str
+    } else if class.is(vm.ctx.types.int_type) {
+        Elem::Int
+    } else if class.is(vm.ctx.types.float_type) {
+        Elem::Float
+    } else if let Some(f) = class.slots.richcompare.load() {
+        Elem::Object(f)
+    } else {
+        Elem::Generic
+    }
+}
+
+fn pre_sort_check<'a>(
+    mut keys: impl Iterator<Item = &'a PyObjectRef>,
+    vm: &VirtualMachine,
+) -> PreSort {
+    let Some(first) = keys.next() else {
+        return PreSort::Generic;
+    };
+
+    if let Some(t) = first
+        .downcast_ref_if_exact::<PyTuple>(vm)
+        .filter(|t| !t.as_slice().is_empty())
+    {
+        pre_sort_check_tuples(&t.as_slice()[0], keys, vm)
+    } else {
+        let class = first.class();
+        if keys.all(|k| k.class().is(class)) {
+            classify(class, vm).into()
+        } else {
+            PreSort::Generic
+        }
+    }
+}
+
+fn pre_sort_check_tuples<'a>(
+    first_elem: &PyObjectRef,
+    keys: impl Iterator<Item = &'a PyObjectRef>,
+    vm: &VirtualMachine,
+) -> PreSort {
+    let class = first_elem.class();
+    let mut all_same_type = true;
+
+    for k in keys {
+        let Some(t) = k
+            .downcast_ref_if_exact::<PyTuple>(vm)
+            .filter(|t| !t.as_slice().is_empty())
+        else {
+            return PreSort::Generic;
+        };
+        if all_same_type && !t.as_slice()[0].class().is(class) {
+            all_same_type = false;
+        }
+    }
+
+    let elem = if !all_same_type || class.is(vm.ctx.types.tuple_type) {
+        Elem::Generic
+    } else {
+        classify(class, vm)
+    };
+    PreSort::Tuple(elem)
+}
+
+fn str_lt(a: &PyObjectRef, b: &PyObjectRef) -> bool {
+    a.downcast_ref::<PyStr>().unwrap().as_bytes() < b.downcast_ref::<PyStr>().unwrap().as_bytes()
+}
+
+fn int_lt(a: &PyObjectRef, b: &PyObjectRef) -> bool {
+    a.downcast_ref::<PyInt>().unwrap().as_bigint() < b.downcast_ref::<PyInt>().unwrap().as_bigint()
+}
+
+fn float_lt(a: &PyObjectRef, b: &PyObjectRef) -> bool {
+    a.downcast_ref::<PyFloat>().unwrap().to_f64() < b.downcast_ref::<PyFloat>().unwrap().to_f64()
+}
+
+fn object_lt(
+    cmp: RichCompareFunc,
+    a: &PyObjectRef,
+    b: &PyObjectRef,
+    vm: &VirtualMachine,
+) -> PyResult<bool> {
+    #[allow(unpredictable_function_pointer_comparisons)]
+    if a.class().slots.richcompare.load() != Some(cmp) {
+        return a.rich_compare_bool(b, PyComparisonOp::Lt, vm);
+    }
+    match cmp(a, b, PyComparisonOp::Lt, vm)? {
+        Either::B(PyComparisonValue::Implemented(v)) => Ok(v),
+        Either::B(PyComparisonValue::NotImplemented) => {
+            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
+        }
+        Either::A(obj) => {
+            if obj.is(&vm.ctx.not_implemented) {
+                a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
+            } else {
+                obj.try_to_bool(vm)
+            }
+        }
+    }
+}
+
+fn elem_lt(elem: &Elem, a: &PyObjectRef, b: &PyObjectRef, vm: &VirtualMachine) -> PyResult<bool> {
+    match elem {
+        Elem::Str => Ok(str_lt(a, b)),
+        Elem::Int => Ok(int_lt(a, b)),
+        Elem::Float => Ok(float_lt(a, b)),
+        Elem::Object(f) => object_lt(*f, a, b, vm),
+        Elem::Generic => a.rich_compare_bool(b, PyComparisonOp::Lt, vm),
+    }
+}
+
+fn tuple_lt(elem: &Elem, a: &PyObjectRef, b: &PyObjectRef, vm: &VirtualMachine) -> PyResult<bool> {
+    let a = a.downcast_ref::<PyTuple>().unwrap().as_slice();
+    let b = b.downcast_ref::<PyTuple>().unwrap().as_slice();
+
+    let mut i = 0;
+    while i < a.len() && i < b.len() {
+        if !a[i].rich_compare_bool(&b[i], PyComparisonOp::Eq, vm)? {
+            break;
+        }
+        i += 1;
+    }
+    if i >= a.len() || i >= b.len() {
+        return Ok(a.len() < b.len());
+    }
+    if i == 0 {
+        elem_lt(elem, &a[0], &b[0], vm)
+    } else {
+        a[i].rich_compare_bool(&b[i], PyComparisonOp::Lt, vm)
+    }
+}
+
+fn timsort_specialized<T, K>(
+    vm: &VirtualMachine,
+    items: &mut [T],
+    reverse: bool,
+    key: K,
+) -> PyResult<()>
+where
+    T: Clone,
+    K: Fn(&T) -> &PyObjectRef,
+{
+    match pre_sort_check(items.iter().map(&key), vm) {
+        PreSort::Str => timsort(items, &mut |a, b| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            Ok(str_lt(a, b))
+        }),
+        PreSort::Int => timsort(items, &mut |a, b| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            Ok(int_lt(a, b))
+        }),
+        PreSort::Float => timsort(items, &mut |a, b| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            Ok(float_lt(a, b))
+        }),
+        PreSort::Object(cmp) => timsort(items, &mut |a, b| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            object_lt(cmp, a, b, vm)
+        }),
+        PreSort::Tuple(elem) => timsort(items, &mut |a, b| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            tuple_lt(&elem, a, b, vm)
+        }),
+        PreSort::Generic => timsort(items, &mut |a, b| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
+        }),
+    }
-    match pre_sort_check(items.iter().map(&key), vm) {
-        PreSort::Str => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            Ok(str_lt(a, b))
-        }),
-        PreSort::Int => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            Ok(int_lt(a, b))
-        }),
-        PreSort::Float => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            Ok(float_lt(a, b))
-        }),
-        PreSort::Object(cmp) => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            object_lt(cmp, a, b, vm)
-        }),
-        PreSort::Tuple(elem) => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            tuple_lt(&elem, a, b, vm)
-        }),
-        PreSort::Generic => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
-        }),
-    }
+    // Wraps a key-level comparison into an item-level one, applying `reverse`
+    // by swapping the operands.
+    let run = |items: &mut [T], lt: &mut dyn FnMut(&PyObjectRef, &PyObjectRef) -> PyResult<bool>| {
+        timsort(items, &mut |a: &T, b: &T| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            lt(a, b)
+        })
+    };
+
+    match pre_sort_check(items.iter().map(&key), vm) {
+        PreSort::Str => run(items, &mut |a, b| Ok(str_lt(a, b))),
+        PreSort::Int => run(items, &mut |a, b| Ok(int_lt(a, b))),
+        PreSort::Float => run(items, &mut |a, b| Ok(float_lt(a, b))),
+        PreSort::Object(cmp) => run(items, &mut |a, b| object_lt(cmp, a, b, vm)),
+        PreSort::Tuple(elem) => run(items, &mut |a, b| tuple_lt(&elem, a, b, vm)),
+        PreSort::Generic => run(items, &mut |a, b| {
+            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
+        }),
+    }
-    match pre_sort_check(items.iter().map(&key), vm) {
-        PreSort::Str => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            Ok(str_lt(a, b))
-        }),
-        PreSort::Int => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            Ok(int_lt(a, b))
-        }),
-        PreSort::Float => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            Ok(float_lt(a, b))
-        }),
-        PreSort::Object(cmp) => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            object_lt(cmp, a, b, vm)
-        }),
-        PreSort::Tuple(elem) => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            tuple_lt(&elem, a, b, vm)
-        }),
-        PreSort::Generic => timsort(items, &mut |a, b| {
-            let (a, b) = if reverse {
-                (key(b), key(a))
-            } else {
-                (key(a), key(b))
-            };
-            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
-        }),
-    }
+    // Wraps a key-level comparison into an item-level one, applying `reverse`
+    // by swapping the operands.
+    let run = |items: &mut [T], lt: &mut dyn FnMut(&PyObjectRef, &PyObjectRef) -> PyResult<bool>| {
+        timsort(items, &mut |a: &T, b: &T| {
+            let (a, b) = if reverse {
+                (key(b), key(a))
+            } else {
+                (key(a), key(b))
+            };
+            lt(a, b)
+        })
+    };
+
+    match pre_sort_check(items.iter().map(&key), vm) {
+        PreSort::Str => run(items, &mut |a, b| Ok(str_lt(a, b))),
+        PreSort::Int => run(items, &mut |a, b| Ok(int_lt(a, b))),
+        PreSort::Float => run(items, &mut |a, b| Ok(float_lt(a, b))),
+        PreSort::Object(cmp) => run(items, &mut |a, b| object_lt(cmp, a, b, vm)),
+        PreSort::Tuple(elem) => run(items, &mut |a, b| tuple_lt(&elem, a, b, vm)),
+        PreSort::Generic => run(items, &mut |a, b| {
+            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
+        }),
+    }
+}
+
 fn do_sort(
     vm: &VirtualMachine,
     values: &mut Vec<PyObjectRef>,
     key_func: Option<PyObjectRef>,
     reverse: bool,
 ) -> PyResult<()> {
-    // CPython uses __lt__ for all comparisons in sort.
-    // try_sort_by_gt expects is_gt(a, b) = true when a should come AFTER b.
-    let cmp = |a: &PyObjectRef, b: &PyObjectRef| {
-        if reverse {
-            // Descending: a comes after b when a < b
-            a.rich_compare_bool(b, PyComparisonOp::Lt, vm)
-        } else {
-            // Ascending: a comes after b when b < a
-            b.rich_compare_bool(a, PyComparisonOp::Lt, vm)
-        }
-    };
-
     if let Some(ref key_func) = key_func {
         let mut items = values
             .iter()
             .map(|x| Ok((x.clone(), key_func.call((x.clone(),), vm)?)))
             .collect::<Result<Vec<_>, _>>()?;
-        timsort::try_sort_by_gt(&mut items, |a, b| cmp(&a.1, &b.1))?;
+        timsort_specialized(
+            vm,
+            &mut items,
+            reverse,
+            |item: &(PyObjectRef, PyObjectRef)| &item.1,
+        )?;
         *values = items.into_iter().map(|(val, _)| val).collect();
     } else {
-        timsort::try_sort_by_gt(values, cmp)?;
+        timsort_specialized(vm, values, reverse, |x: &PyObjectRef| x)?
     }
 
     Ok(())

diff --git a/crates/vm/src/lib.rs b/crates/vm/src/lib.rs
@@ -92,6 +92,7 @@ pub mod scope;
 pub mod sequence;
 pub mod signal;
 pub mod sliceable;
+pub mod sorting;
 pub mod stdlib;
 pub mod suggestion;
 pub mod types;