Tracking Issue for unstable sorting in const context

[onestacked]

Feature gate: #![feature(const_sort)]

This is a tracking issue for const slice::sort_unstable and sort_internals.

Public API

// core::slice

pub const fn heapsort<T, F>(v: &mut [T], mut is_less: F)
where
    F: ~const FnMut(&T, &T) -> bool + ~const Destruct;

pub const fn sort_unstable(&mut self)
    where
        T: ~const Ord;

 pub const fn sort_unstable_by<F>(&mut self, mut compare: F)
    where
        F: ~const FnMut(&T, &T) -> Ordering + ~const Destruct;

pub const fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
    where
        F: ~const FnMut(&T) -> K + ~const Destruct,
        K: ~const Ord + ~const Destruct;

pub const fn select_nth_unstable(&mut self, index: usize) -> (&mut [T], &mut T, &mut [T])
    where
        T: ~const Ord;

 pub const fn select_nth_unstable_by<F>(
        &mut self,
        index: usize,
        mut compare: F,
    ) -> (&mut [T], &mut T, &mut [T])
    where
        F: ~const FnMut(&T, &T) -> Ordering + ~const Destruct;

pub const fn select_nth_unstable_by_key<K, F>(
        &mut self,
        index: usize,
        mut f: F,
    ) -> (&mut [T], &mut T, &mut [T])
    where
        F: ~const FnMut(&T) -> K + ~const Destruct,
        K: ~const Ord + ~const Destruct;

pub const fn is_sorted(&self) -> bool
    where
        T: ~const PartialOrd;

pub const fn is_sorted_by<F>(&self, mut compare: F) -> bool
    where
        F: ~const FnMut(&T, &T) -> Option<Ordering> + ~const Destruct;

pub const fn is_sorted_by_key<F, K>(&self, mut f: F) -> bool
    where
        F: ~const FnMut(&T) -> K + ~const Destruct,
        K: ~const PartialOrd + ~const Destruct;

slice::sort[_by[_key]] would need allocations in const context to be implemented. #79597

Steps / History

• Implementation: [WIP] Constified slice::sort_unstable, sort_internals #102279
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• See [WIP] Constified slice::sort_unstable, sort_internals #102279

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[est31]

Can you maybe add ... in core to this? And mention why slice::sort is not included? I guess it's not included because it's in alloc due to using merge_sort which allocates internally. Edit: Resolved, thanks!