use crate::backend_ops::BackendOps;
use coeus_core::{CpuAddressableStorage, CpuAddressableStorageMut, Scalar};
use coeus_tensor::Tensor;
#[inline]
#[expect(
clippy::type_complexity,
reason = "the established sort contract returns sorted values and source indices together"
)]
pub fn sort<T: Scalar + PartialOrd + coeus_core::TryFromCount, B: BackendOps<T> + Default>(
input: &Tensor<T, B>,
axis: usize,
descending: bool,
backend: &B,
) -> Result<(Tensor<T, B>, Tensor<T, B>), B::Error>
where
B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
{
let ndim = input.ndim();
assert!(
axis < ndim,
"sort: axis {axis} out of range for {ndim}-D tensor"
);
let shape = input.shape().to_vec();
let axis_len = shape[axis];
let outer: usize = shape[..axis].iter().product();
let inner: usize = shape[axis + 1..].iter().product();
let numel: usize = shape.iter().product();
let mut out_vals = vec![T::ZERO; numel];
let mut out_idx = vec![T::ZERO; numel];
for o in 0..outer {
for i in 0..inner {
let mut pairs: Vec<(T, usize)> = (0..axis_len)
.map(|a| {
let flat = o * (axis_len * inner) + a * inner + i;
let val = input.get(&crate::shape::flat_to_nd(flat, &shape));
(val, a)
})
.collect();
pairs.sort_by(|(va, _), (vb, _)| {
let ord = va.partial_cmp(vb).unwrap_or(std::cmp::Ordering::Equal);
if descending {
ord.reverse()
} else {
ord
}
});
for (a, (val, orig_idx)) in pairs.into_iter().enumerate() {
let flat = o * (axis_len * inner) + a * inner + i;
out_vals[flat] = val;
out_idx[flat] =
T::try_from_count(orig_idx).expect("sort axis positions fit the element type");
}
}
}
Ok((
Tensor::from_slice_on(shape.clone(), &out_vals, backend)?,
Tensor::from_slice_on(shape, &out_idx, backend)?,
))
}