Welcome, dear readers, to a brand new Deep Dive series! This one is quite possibly the nerdiest thing I have ever blogged about. It's also the reason there hasn't been as many posts as normal lately; I've been working on it for nearly a month.
Without further ado, welcome to The Sorting Algorithm Family Reunion!
(What? I did say "nerdiest", didn't I?)
In this series of posts we will be investigating a set of sorting algorithms, from simple Selection Sort to complex Bitonic Merge Sort to stupid Bogosort. For each algorithm, we will include the following sections:
- The Rundown: Statistics about the algorithm, including its time and space complexities, creator name and date, sort type, etc.
- Algorithm: A numbered set of steps that outlines how the algorithm accomplishes sorting.
- Visualization: A manner in which we can "see" how the algorithm performs. May be an animation, a set of diagrams, a walkthrough, etc.
- C# Implementation: The C# implementation of the algorithm, including comments. All implementations are hosted on GitHub.
- Time and Space Complexity: A discussion about what the time and space complexities (using Big-O Notation) of the algorithm mean for its implementations.
Yes, dear readers, in order to write about a family reunion I had to create a family tree. Here's the one we'll be using:
An Important Note
The family tree above DOES NOT relate sorting methods by their algorithmic characteristics; it relates them by my ability to create stories and backgrounds. For example, you should not assume that because Pigeonhole Sort is the child of Merge and Selection Sorts that those algorithms are conceptually related in any way.
The reasoning for this is that it was impossible, within the framework of the story, to create a cohesive family tree that kept all of the algorithmic relationships alive. I chose to use some, shall we say, "artistic license" to keep the story intact. That said, there are many cases where the algorithms are indeed related, and where that happens I will make an effort to point it out in the posts themselves.
I'll be releasing a new post in this series every Monday and Thursday until I run out of posts (excepting Labor Day in the U.S.) Here's the current release schedule (all dates in 2019):
Jul 18: Selection Sort
Jul 22: Merge Sort
Jul 25: Insertion Sort
Jul 29: Shell Sort
Aug 1: Comb Sort
Aug 5: Quick Sort
Aug 8: Heap Sort
Aug 12: Cocktail Shaker Sort
Aug 15: Bogo Sort
Aug 19: Bubble Sort
Aug 22: Odd-Even Sort
Aug 26: Counting Sort
Aug 29: Bitonic Merge Sort
Sep 5: Pigeonhole Sort
Sep 9: Gnome Sort
Sep 12: Radix Sort
Sep 16: Bucket Sort
Thanks for Reading!
This series has been quite a lot of work to write and plan, but now that it's ready for publication, I'm pretty proud of it. Don't forget to check out the sample project over on GitHub, and as always, thanks for reading!