912. Sort an Array

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Merge sort (ping-pong buffer):

#![allow(unused)]
fn main() {
// time O(n log n), space O(n)
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
    let mut scratch = nums.clone();
    merge_sort(&mut nums, &mut scratch);
    nums
}

fn merge_sort(dst: &mut [i32], scratch: &mut [i32]) {
    if dst.len() <= 1 {
        return;
    }

    let mid = dst.len() / 2;
    let (dst_left, dst_right) = dst.split_at_mut(mid);
    let (buf_left, buf_right) = scratch.split_at_mut(mid);

    merge_sort(buf_left, dst_left);
    merge_sort(buf_right, dst_right);

    merge(buf_left, buf_right, dst);
}

fn merge(left: &[i32], right: &[i32], out: &mut [i32]) {
    let (mut i, mut j, mut k) = (0, 0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            out[k] = left[i];
            i += 1;
        } else {
            out[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    out[k..].copy_from_slice(if i < left.len() {
        &left[i..]
    } else {
        &right[j..]
    });
}
}

Counting sort:

#![allow(unused)]
fn main() {
// time O(n + range), space O(range)
pub fn sort_array_counting(mut nums: Vec<i32>) -> Vec<i32> {
    let Some((min, max)) = min_max(&nums) else {
        return nums;
    };

    let span = (max as i64 - min as i64 + 1) as usize;
    let mut cnt = vec![0u32; span];

    for &x in &nums {
        cnt[(x - min) as usize] += 1;
    }

    let mut k = 0;
    for (offset, &count) in cnt.iter().enumerate() {
        let count = count as usize;
        nums[k..k + count].fill(min + offset as i32);
        k += count;
    }

    nums
}

fn min_max(v: &[i32]) -> Option<(i32, i32)> {
    let mut it = v.iter().copied();
    let first = it.next()?;
    Some(it.fold((first, first), |(lo, hi), x| (lo.min(x), hi.max(x))))
}
}

Quicksort (randomized pivot, three-way partition):

#![allow(unused)]
fn main() {
// time O(n log n) expected, space O(log n) expected
pub fn sort_array_quicksort(mut nums: Vec<i32>) -> Vec<i32> {
    let mut rng = Rng::new();
    quicksort(&mut nums, &mut rng);
    nums
}

fn quicksort(v: &mut [i32], rng: &mut Rng) {
    if v.len() <= 1 {
        return;
    }

    let pivot = v[rng.below(v.len())];
    let (lt, gt) = partition(v, pivot);

    let (less, rest) = v.split_at_mut(lt);
    let (_equal, greater) = rest.split_at_mut(gt - lt);

    quicksort(less, rng);
    quicksort(greater, rng);
}

fn partition(v: &mut [i32], pivot: i32) -> (usize, usize) {
    let (mut lt, mut i, mut gt) = (0, 0, v.len());
    while i < gt {
        if v[i] < pivot {
            v.swap(lt, i);
            lt += 1;
            i += 1;
        } else if v[i] > pivot {
            gt -= 1;
            v.swap(i, gt);
        } else {
            i += 1;
        }
    }

    (lt, gt)
}

struct Rng(u64);

impl Rng {
    fn new() -> Self {
        Rng(RandomState::new().build_hasher().finish() | 1)
    }

    fn next_u64(&mut self) -> u64 {
        let mut x = self.0;
        x ^= x >> 12;
        x ^= x << 25;
        x ^= x >> 27;
        self.0 = x;
        x.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }

    fn below(&mut self, n: usize) -> usize {
        ((self.next_u64() as u128 * n as u128) >> 64) as usize
    }
}
}