Sorting Algorithms: Implementing Insertion Sort Using Swift

In the previous article, we took a swing at analyzing and implementing Bubble Sort. In today’s article, we are going to take a look at a sorting algorithm best known as Insertion Sort, and see how it operates under the hood.

XCode Playground Files with implementations are available on this link.

What Is Insertion Sort?

Insertion Sort takes inspiration from the way you would sort a hand of shuffled cards. You start at the second card and compare it to the first card. If the second card is smaller, you shift it over one spot to the left, else you leave it and move on to the third card. While the card you’re currently sorting is smaller than the one before it, you shift it over one spot. Once you’ve moved all the way up to the last card and shifted that into place, the hand will be sorted. Let’s see how we would translate this idea into sorting an array of integers. Take a look at the sketch below (the arrow marks the element we’re currently sorting, and the curly brace marks the part of the array that we’re currently working with):