Let’s sort this out: Mergesort algorithm
As a developer or software engineer, it’s expected that you know about algorithms (in addition to data structures). It’s well known that you will be asked questions about them in interviews and there are countless references available to improve your knowledge on them. After hearing so much about them, I wanted to know more and I decided to start with sorting algorithms.
Mergesort is referred to as a divide and conquer algorithm which uses recursion to sort the given input (recursion just means that a function calls on itself). I found that the clearest way to understand the algorithm is with a diagram of how it works, as shown below.
The array is repeatedly split in half (the dividing aspect of the algorithm) into new arrays until each array contains only one element. Then, these one element arrays merge, forming new arrays containing the elements in the sorted order. This merging and sorting (the conquering aspect of the algorithm) continues until only one array is left that contains the sorted output.
Any discussion of algorithms would be incomplete without an understanding of big O notation. Big O notation is used to compare the various algorithms that exist and is based on how quickly the runtime increases as the size of the input increases. If you have a small array, such as one containing 10 elements, you probably won’t notice much of a difference between the different algorithms. However, if you have an array with thousands of elements, the runtime of an algorithm becomes a more important consideration.
When it comes to big O notation, it can be a bit difficult to visualize depending on your math background. I found a nice graph (as shown below) that clearly compares the influence of input size and how that relates to the growth rate of the runtime for the different complexities.
As you’ll notice in the table above, the average time complexity of selection sort, mergesort, quicksort, and heapsort are all O(n log n). They do differ in space complexity, with smooth sort and heapsort using the least amount of memory. This is influenced by whether the algorithm sorts in-place or not. In-place sorting algorithms don’t require any additional data structures as it runs (i.e. in quicksort, elements are rearranged within the input array, as opposed to mergesort, where the input array is divided into additional arrays).
In addition to time and space complexity, it is important to consider stability. The stability of sorting algorithms describes how the algorithm handles elements with the same key. If the sorted output maintains these elements in the same order as the unsorted input, then the algorithm is said to be stable. For example, let’s say we want to alphabetically sort an array by the first letter of each word, where the initial input is: [“latte”, “americano, “cappuccino”, “mocha”, “coffee”]. The output of a stable sorting algorithm would be: [“americano”, “cappuccino”, “coffee”, “latte”, “mocha”]. In an unstable algorithm, the output could be [“americano”, “cappuccino”, “coffee”, “latte”, “mocha”] or [“americano”, “coffee”, “cappuccino”, “latte”, “mocha”].
Ultimately, there are a lot of factors to consider when selecting which sorting algorithm to use, including the size of your input, whether time or space is a higher priority, if the input is already partially sorted, etc.
