Insertion Sort in Swift

Insertion Sort is a simple sorting algorithm runs in О(n²) time. It is less efficient than Quick Sort, Merge Sort or Heap Sort on larger datasets. But it is an efficient algorithm while inserting items to an already sorted dataset.

Define the problem and the algorithm interface

Using generics enables us to use insertionSort function to sort all arrays having items implementingComparable protocol. array defined as inout variable to make in-place changes on array.

Divide the sorting problem

Dividing sorting problem changes the sorting problem into an insertion problem. You need to implement an insert function that takes arguments:

• array which has sorted and unsorted parts
• rightIndex the index of the last inserted (or sorted) element,
• value the value of the item to insert

If you implement an insert function which transfers the items one by one from unsorted part of the array to the sorted part, the sorting problem will be solved by inserting items.

Conquer the item insertion problem

Time to conquer the problem for one item. insertionSort function will call insert for all items except the zeroth item (since it is not needed to sort an array with one item) so you just need to worry about the value at hand while implementing insert.

You need to shift right all items bigger than the value unless index takes a value equal to / smaller than zero. At the end you set the item to the first location where value is bigger than the compared array item. (if value is smaller than the all items compared, value is set to array[0])

Merge

Since you are doing changes on the actual dataset, and inserting each element to it’s location in the dataset. You don’t need a merge stage for Insertion Sort algorithm.

Finishing touch

Insertion sort algorithm is ready but a small refinement can make it better.

Add a check for empty array

Currently our insertion sort algorithm will crash if you try to sort an empty array. By adding a check you can fix this issue.

Download InsertionSort.playground to see the full source code in action.

Happy coding.