Insertion Sort in Swift

The classic sorted and unsorted sub arrays

Steven Curtis

2 min readMay 28

Difficulty: Beginner* | Easy | Normal | Challenging

This article covers the classic sorting algorithm Merge Sort, and it’s implementation in Swift.

This is seen as a beginner topic (first year Computer Science degree fare) but is certainly not easy.

Terminology

Algorithm: A process or set of rules to be followed

Big O Notation: A mathematical notation to describe the limiting behaviour of a function when an argument tends towards infinity

Insertion Sort: A sort where the first element is taken from an unsorted sublist, and inserted into the correct position in the sorted sublist

Insertion Sort

The insertion sort algorithm involves splitting our array into a sorted sublist, and an unsorted sublist (in our initial array — we aren’t doing anything clever with our input array in any way.

So initially our sorted subarray is empty ([]) but the unsorted subarray has the whole initial array in it!

Let us follow the algorithm step-by-step — we are moving each element in turn to the right place in the sorted sublist.

The tests and function signature

A good function header to choose for our selection sort is as follows:

func func insertionSort(_ inputArray: [Int]) -> [Int]

This gives us the opportunity to run the following tests. Since I’m completing this in the Playground, I’ll need to import XCTest and at the bottom of the code sortingTests.defaultTestSuite.run() to run the following tests:

The implementation

The time complexity

Insertion sort is considered to be an O(n²) algorithm, as it has a nested loop

Conclusion

Insertion sort is a relatively simple sorting algorithm. It can be used to sort, although in Swift we often use the in built .sort() algorithm that gets the job done!