Sorting Algorithms in F#

Yan Cui

I help clients go faster for less using serverless technologies.

After a long Easter holiday filled with late night coding sessions I find myself wide awake at 2am… good job I’ve still got my pluralsight subscription and a quick look at the Algorithms and Data Structures course again at least gave me something to do to relax the mind with some back-to-school style implementation of common sorting algorithms in F#:

Whilst not the most performant implementations I’m sure, I hope at least it goes to show how easily and concisely these simple algorithms can be expressed in F#! Now back to that sleep thing…

Whenever you’re ready, here are 4 ways I can help you:

  1. Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
  2. Do you want to know how to test serverless architectures with a fast dev & test loop? Check out my latest course, Testing Serverless Architectures and learn the smart way to test serverless.
  3. I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
  4. Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.

2 thoughts on “Sorting Algorithms in F#”

  1. Nice but I think Quicksort should use in-place partition in accordance with Hoare’s explanation in his original Quicksort paper otherwise you’ve taken the “quick” out of “quicksort”.

  2. theburningmonk

    @Jon Harrop – thanks, you’re absolutely right, I’ve gone back and added the in-place version of quick sort now as well.

    For an array of 1 million elements [| 1000000..-1..1 |], the simple version fails with OutOfMemoryException after quite some time, but the in-place version takes under 3 seconds to execute on my machine. When marked with inline (final version above) the same array takes around 150ms to run – a marked improvement!

    That said, the built-in Array.sort function manages to sort the same 1-million element array in around 40ms, pretty impressive :-)

Leave a Comment

Your email address will not be published. Required fields are marked *