Algorithm Series Part II: Sorting Algorithms

One of the most common uses of an algorithm in programming and Computer Science is to sort things. Sorting is a problem we have in everyday life and programming is no different. There are many different ways to sort items and the trick is finding the most efficient way. Two common sorting algorithms used today are Bubble Sort and Merge Sort. Both algorithms take two different approaches to the same problem with varying efficiencies.

I. Bubble Sort

Bubble Sort is a fairly straightforward algorithm. To begin, let's say we have a list of numbers in random order: 4, 2, 7, 9, 11, 3. Now without thinking about code, how could we sort this? Well, let's say we want to sort these numbers in ascending order with the smallest number first and the largest number last. We could compare each number to the next number and see if it’s larger or smaller. That’s how the Bubble Sort algorithm works. It looks at each number and compares it to the next. If the next number is smaller than the first number, they swap places. The algorithm continues comparing each number until the list is sorted in the right order.

Here’s an example of Bubble Sort written in Javascript.

function bubbleSort(array) {

let isSorted = false;
while (!isSorted) {
isSorted = true;
for (let i = 0; i < array.length - 1; i++)
if (array[i] > array[i + 1]) {
swap(i, i + 1, array);
isSorted = false;
}
}
return array;
}
function swap(i, j, array) {
let temp = array[j];
array[j] = array[i];
array[i] = temp;
}

Let’s take this apart. We’re first declaring a variable, isSorted, which we initialize to false. Next, we use a while loop and perform actions as long as isSorted remains false. Now you may notice we have a nested loop. Here we iterate through the input array once. We have an if check which checks to see if the current element we’re looking at is larger than the one to the right of it. If so, we want to swap the elements. Also in the if check, we reset isSorted to false because if we make it into the if check, our array is not yet sorted. Once our variable isSorted remains true, we exit our loop and we’re done. Our array is now sorted in the correct order. This is a fairly straightforward algorithm. We check to see if each element is larger or smaller than the element to the right and we swap accordingly. Now let’s discuss the time complexity of this algorithm.

From a prior blog, I discussed time complexity, so if you’re unsure about big o notation, no problem, check out this blog and come back. Because we have a nested loop, the number of times the expressions in the nested loop will run will be O(n²). While Bubble Sort is fairly easy to understand, for larger inputs it might be too slow. Another algorithm that has a more optimal time complexity — but is more complex is Merge Sort.

II. Merge Sort

Merge Sort is a bit different than Bubble Sort in that instead of comparing each element in an array, Merge Sort breaks the array into small sub-arrays and uses a concept called recursion to sort the sub-arrays before merging them all back together. Recursion is a concept where the function or in or case the algorithm calls itself. To prevent a function from repeatedly calling itself, we have to have a base case or an expression that eventually stops the recursive action. Below is an example of Merge Sort in practice.

function sort(array) {
if (array.length < 2) {
return array;
}
if ((array.length === 2)) {
return array[0] > array[1] ? [array[1], array[0]] : array;
}
const middle = Math.floor(array.length / 2);
const leftArray = array.slice(0, middle);
const rightArray = array.slice(middle);

const leftSortedArray = sort(leftArray);
const rightSortedArray = sort(rightArray);

const mergedArray = [];
let leftArrayIndex = 0;
let rightArrayIndex = 0;

while (
leftArrayIndex < leftSortedArray.length ||
rightArrayIndex < rightSortedArray.length
) {
if(leftArrayIndex >= leftSortedArray.length || leftSortedArray[leftArrayIndex] > rightSortedArray[rightArrayIndex]) {
mergedArray.push(rightSortedArray[rightArrayIndex])
rightArrayIndex++
} else {
mergedArray.push(leftSortedArray[leftArrayIndex])
leftArrayIndex++
}
}
return mergedArray;
}

This algorithm looks complex, but when we break it down it gets easier to understand. The first expression handles edge cases. If the input array is less than two, it’s already sorted because there is either one element or none. We only have to worry about input arrays greater than two. With inputs that are exactly two, we can do something similar to Bubble Sort and just check if one element is greater than another and swap accordingly.

With input arrays greater than two elements, we’ll first want to split our array in half. To account for odd number arrays, we can use Math. floor. We use the slice function in Javascript to create two new arrays. The first will contain elements to the left of the middle element and the right array contains elements to the right of the middle element. Next, we create two new elements and set them equal to the recursive process of breaking our two newly created arrays into chunks.

You can see that we’re using a while loop to iterate through our two arrays. We then have and if check to see whether the left index value is greater than the right index value. If this is the case, we want to add the right index value to our merged array and increment the right index to compare the following right index with the left index. We also have a condition that checks if the left array has been iterated through already. Because of how we split up the array, the left array will always be equal or greater than the right array. If the left array is greater than the right array, we simply want to add the remaining values from the right array to our merged array. Now, with our recursive steps, the algorithm will continue to run until the split arrays contain less than two values. When that’s the case, we simply return the array. That’s the crux of Merge Sort. A little more complicated to understand than Bubble Sort, but you may already tell, that it might perform better on larger inputs. Let’s explore that.

We do have a nested loop, which from prior discussion might lead you to the conclusion that the Merge Sort time-complexity is O(n²). However, that’s not quite right. Because we’re continuously splitting the input array and iterating over the smaller and smaller array’s the time-complexity is actually O(n log n).

That will do it for this brief intro into sorting algorithms. You can see that Merge Sort performs better on larger inputs than Bubble Sort, but if you have a small input, Bubble Sort might be easier to implement. I’ve attached some other articles that have helped me understand these concepts and hopefully will help you, too.

Resources

Software Engineering Student

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store