Insertion Sort in Swift

The classic sorted and unsorted sub arrays

Photo by KAL VISUALS on Unsplash

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.