# Insertion Sort in Swift

## The classic sorted and unsorted sub arrays

--

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 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!