Stackoverflow using split_at_mut

HI, I am currently trying to implement quicksort using recursion, but I kept getting stackoverflow when I use split_at_mut but works fine if I use &buf[0..pivot_idx] and &buf[pivot_idx+1..len] it works fine. I would like to know if I am misunderstanding something here or there's more to it Here's the code. Thanks!

pub struct QuickSort;

impl QuickSort {
    pub fn partition<T: Ord + Copy>(buf: &mut [T]) -> usize {
        // we use the middle as the pivot element
        let mid = buf.len() / 2;

        // we swap the pivot with the first element in the list
        let pivot = buf[mid];
        buf.swap(0, mid);

        // set to the first item in buf
        // usually in other languages we use the int passed into the function
        let mut last_small = 0;

        // in this case, we are moving all the elements smaller than pivot
        // to the left
        // which also makes the right automatically bigger than the pivot
        for i in 1..buf.len() {
            if buf[i] < pivot {
                // last_small go next first
                last_small += 1;
                buf.swap(last_small, i);
            }
        }

        // we swap back the pivot back to the original position
        buf.swap(0, last_small);

        last_small
    }

    pub fn sort<T: Ord + Copy>(buf: &mut [T]) {
        if !buf.is_empty() {
            let pivot_idx = Self::partition(buf);
            let sz = buf.len();
            // QuickSort::sort(&mut buf[0..pivot_idx]);
            // QuickSort::sort(&mut buf[pivot_idx+1..sz]);
            let (l_buf, r_buf) = buf.split_at_mut(pivot_idx);
            QuickSort::sort(l_buf);
            QuickSort::sort(r_buf);
        }
    }
}

The splitting version doesn't exclude the pivot. The second recursive call should take &mut r_buf[1..].

(Incidentally, this likely means that there should be a check for an empty subslice, too.)

2 Likes

Thanks for the fast reply! I guess it was a misunderstanding of the algorithm that I should not include the pivot

If you include the pivot, then you will always try to sort at least one element, so you never hit the empty base case. (Of course, a singleton slice could also be the base case, since you don't need to sort it either.)

1 Like