Implementing quicksort in a functional way

1

I know that it's a bad idea to use my own sort implementation but out of interest...

What could be improved about this (hopefully) functional quicksort implementation?

fn quick_sort<T, E>(mut v: T) -> Vec<E>
    where T: Iterator<Item=E>,
    E: PartialOrd
{
    let pivot = match v.next() {
        Some(p) => p,
        None => return Vec::new()
    };
    
    let (lower, higher): (Vec<_>, Vec<_>) = v.partition(|it| it < &pivot);
    let lower = quick_sort(lower.into_iter());
    let higher = quick_sort(higher.into_iter());
    lower.into_iter()
    .chain(core::iter::once(pivot))
    .chain(higher.into_iter()).collect::<Vec<E>>()
}
1 Like
2

As far as functional programming goes this looks quite clean and well done.

The thing that jumps out at me is your partition() call. Every time you go through the quick_sort() function you'll be allocating a pair of temporary vectors and populating it with references to the items above/below your pivot. The final .collect::<Vec<E>>() (tip: you don't need turbofish here because it'll be deduced) will drain the contents of your lower and higher buffers, effectively double-handling the data.

I think the problem you're going to encounter is that by using a functional style you'll have loads of unnecessary allocations and copies, which would destroy runtime performance. Functional programming prefers to leave things immutable which means every function will construct and return a new object, so I'm not sure how you'd get around that.

Normally, I'd recommend accepting a &mut [T] as the input parameter and then using something like split_at_mut() to split at your pivot point, but I'm not sure whether that is "functional" enough...

3

I understand your intension of the functional way here, but most functional languages have sort function implemented with mutable buffer under the hood for the performance reason. Quicksort is quick because we don't need extra allocation for it and it's cache friendly.

4

Afaik all decent languages have :wink: (at least I hope so) But I was about learning functional style, not sorting a list.

5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.