just several sorting algorithms. Expand reading: Wikipedia
Overview
Classification
Algorithms usually can be divided into two categories:
 Comparison Sorting: The relative order between elements is determined by comparison, because its time complexity cannot break O(nlogn), so it is also called nonlinear time comparison sorting.
 Noncomparative Sorting: The relative order between elements is not determined by comparison, so it is possible to break through the lower bound of time based on comparison sorting and run in linear time, so it is also called linear noncomparative sorting.
Algorithm complexity
Sorting  TC(avg)  TC(bad)  TC(good)  SC  Stability 

Insertion Sort  $$O(n^2)$$  $$O(n^2)$$  $$O(n)$$  $$O(1)$$  T 
Shell Sort  $$O(n^{1.3})$$  $$O(n^2)$$  $$O(n)$$  $$O(1)$$  F 
Selection Sort  $$O(n^2)$$  $$O(n^2)$$  $$O(n^2)$$  $$O(1)$$  F 
Heap Sort  $$O({nlog}_2n)$$  $$O({nlog}_2n)$$  $$O({nlog}_2n)$$  $$O(1)$$  T 
Bubble Sort  $$O(n^2)$$  $$O(n^2)$$  $$O(n)$$  $$O(1)$$  T 
Quicksort  $$O({nlog}_2n)$$  $$O(n^2)$$  $$O({nlog}_2n)$$  $$O({nlog}_2n)$$  F 
Merge Sort  $$O({nlog}_2n)$$  $$O({nlog}_2n)$$  $$O({nlog}_2n)$$  $$O(n)$$  T 
Counting Sort*  $$O(n+k)$$  $$O(n+k)$$  $$O(n+k)$$  $$O(n+k)$$  T 
Bucket Sort*  $$O(n+k)$$  $$O(n^2)$$  $$O(n)$$  $$O(n+k)$$  T 
Radix Sort  $$O(n+k)$$  $$O(n*k)$$  $$O(n*k)$$  $$O(n*k)$$  T 
It’s fun to see how sorting algorithms work, but in practice you’ll almost never have to provide your own sorting routines.
Basic sorts:
Insertion Sort
Goal: Sort an array from low to high (or high to low).
You are given an array of numbers and need to put them in the right order. The insertion sort algorithm works as follows:
 Put the numbers on a pile. This pile is unsorted.
 Pick a number from the pile. It doesn’t really matter which one you pick, but it’s easiest to pick from the top of the pile.
 Insert this number into a new array.
 Pick the next number from the unsorted pile and also insert that into the new array. It either goes before or after the first number you picked, so that now these two numbers are sorted.
 Again, pick the next number from the pile and insert it into the array in the proper sorted position.
 Keep doing this until there are no more numbers on the pile. You end up with an empty pile and an array that is sorted.
That’s why this is called an “insertion” sort, because you take a number from the pile and insert it in the array in its proper sorted position.
An example
Let’s say the numbers to sort are [ 8, 3, 5, 4, 6 ]
. This is our unsorted pile.
Pick the first number, 8
, and insert it into the new array. There is nothing in that array yet, so that’s easy. The sorted array is now [ 8 ]
and the pile is [ 3, 5, 4, 6 ]
.
Pick the next number from the pile, 3
, and insert it into the sorted array. It should go before the 8
, so the sorted array is now [ 3, 8 ]
and the pile is reduced to [ 5, 4, 6 ]
.
Pick the next number from the pile, 5
, and insert it into the sorted array. It goes in between the 3
and 8
. The sorted array is [ 3, 5, 8 ]
and the pile is [ 4, 6 ]
.
Repeat this process until the pile is empty.
Inplace sort
The above explanation makes it seem like you need two arrays: one for the unsorted pile and one that contains the numbers in sorted order.
But you can perform the insertion sort inplace, without having to create a separate array. You just keep track of which part of the array is sorted already and which part is the unsorted pile.
Initially, the array is [ 8, 3, 5, 4, 6 ]
. The 
bar shows where the sorted portion ends and the pile begins:


This shows that the sorted portion is empty and the pile starts at 8
.
After processing the first number, we have:


The sorted portion is [ 8 ]
and the pile is [ 3, 5, 4, 6 ]
. The 
bar has shifted one position to the right.
This is how the content of the array changes during the sort:


In each step, the 
bar moves up one position. As you can see, the beginning of the array up to the 
is always sorted. The pile shrinks by one and the sorted portion grows by one, until the pile is empty and there are no more unsorted numbers left.
How to insert
At each step you pick the topmost number from the unsorted pile and insert it into the sorted portion of the array. You must put that number in the proper place so that the beginning of the array remains sorted. How does that work?
Let’s say we’ve already done the first few elements and the array looks like this:


The next number to sort is 4
. We need to insert that into the sorted portion [ 3, 5, 8 ]
somewhere.
Here’s one way to do this: Look at the previous element, 8
.


Is this greater than 4
? Yes it is, so the 4
should come before the 8
. We swap these two numbers to get:


We’re not done yet. The new previous element, 5
, is also greater than 4
. We also swap these two numbers:


Again, look at the previous element. Is 3
greater than 4
? No, it is not. That means we’re done with number 4
. The beginning of the array is sorted again.
This was a description of the inner loop of the insertion sort algorithm, which you’ll see in the next section. It inserts the number from the top of the pile into the sorted portion by swapping numbers.
The code
Here is an implementation of insertion sort in Swift:


Put this code in a playground and test it like so:


Here is how the code works.
 Make a copy of the array. This is necessary because we cannot modify the contents of the
array
parameter directly. Like Swift’s ownsort()
, theinsertionSort()
function will return a sorted copy of the original array.  There are two loops inside this function. The outer loop looks at each of the elements in the array in turn; this is what picks the topmost number from the pile. The variable
x
is the index of where the sorted portion ends and the pile begins (the position of the
bar). Remember, at any given moment the beginning of the array – from index 0 up tox
– is always sorted. The rest, from indexx
until the last element, is the unsorted pile.  The inner loop looks at the element at position
x
. This is the number at the top of the pile, and it may be smaller than any of the previous elements. The inner loop steps backwards through the sorted array; every time it finds a previous number that is larger, it swaps them. When the inner loop completes, the beginning of the array is sorted again, and the sorted portion has grown by one element.
Note: The outer loop starts at index 1, not 0. Moving the very first element from the pile to the sorted portion doesn’t actually change anything, so we might as well skip it.
No more swaps
The above version of insertion sort works fine, but it can be made a tiny bit faster by removing the call to swap()
.
You’ve seen that we swap numbers to move the next element into its sorted position:


Instead of swapping with each of the previous elements, we can just shift all those elements one position to the right, and then copy the new number into the right position.


In code that looks like this:


The line at //1
is what shifts up the previous elements by one position. At the end of the inner loop, y
is the destination index for the new number in the sorted portion, and the line at //2
copies this number into place.
Making it generic
It would be nice to sort other things than just numbers. We can make the datatype of the array generic and use a usersupplied function (or closure) to perform the lessthan comparison. This only requires two changes to the code.
The function signature becomes:


The array has type [T]
where T
is the placeholder type for the generics. Now insertionSort()
will accept any kind of array, whether it contains numbers, strings, or something else.
The new parameter isOrderedBefore: (T, T) > Bool
is a function that takes two T
objects and returns true if the first object comes before the second, and false if the second object should come before the first. This is exactly what Swift’s builtin sort()
function does.
The only other change is in the inner loop, which now becomes:


Instead of writing temp < a[y  1]
, we call the isOrderedBefore()
function. It does the exact same thing, except we can now compare any kind of object, not just numbers.
To test this in a playground, do:


The <
and >
determine the sort order, lowtohigh and hightolow, respectively.
Of course, you can also sort other things such as strings,


or even more complex objects:


The closure tells insertionSort()
to sort on the priority
property of the objects.
Insertion sort is a stable sort. A sort is stable when elements that have identical sort keys remain in the same relative order after sorting. This is not important for simple values such as numbers or strings, but it is important when sorting more complex objects. In the example above, if two objects have the same priority
, regardless of the values of their other properties, those two objects don’t get swapped around.
Performance
Insertion sort is really fast if the array is already sorted. That sounds obvious, but this is not true for all search algorithms. In practice, a lot of data will already be largely – if not entirely – sorted and insertion sort works quite well in that case.
The worstcase and average case performance of insertion sort is O(n^2). That’s because there are two nested loops in this function. Other sort algorithms, such as quicksort and merge sort, have O(n log n) performance, which is faster on large inputs.
Insertion sort is actually very fast for sorting small arrays. Some standard libraries have sort functions that switch from a quicksort to insertion sort when the partition size is 10 or less.
I did a quick test comparing our insertionSort()
with Swift’s builtin sort()
. On arrays of about 100 items or so, the difference in speed is tiny. However, as your input becomes larger, O(n^2) quickly starts to perform a lot worse than O(n log n) and insertion sort just can’t keep up.
Selection Sort
Goal: To sort an array from low to high (or high to low).
You are given an array of numbers and need to put them in the right order. The selection sort algorithm divides the array into two parts: the beginning of the array is sorted, while the rest of the array consists of the numbers that still remain to be sorted.


This is similar to insertion sort, but the difference is in how new numbers are added to the sorted portion.
It works as follows:
 Find the lowest number in the array. You must start at index 0, loop through all the numbers in the array, and keep track of what the lowest number is.
 Swap the lowest number with the number at index 0. Now, the sorted portion consists of just the number at index 0.
 Go to index 1.
 Find the lowest number in the rest of the array. This time you start looking from index 1. Again you loop until the end of the array and keep track of the lowest number you come across.
 Swap the lowest number with the number at index 1. Now, the sorted portion contains two numbers and extends from index 0 to index 1.
 Go to index 2.
 Find the lowest number in the rest of the array, starting from index 2, and swap it with the one at index 2. Now, the array is sorted from index 0 to 2; this range contains the three lowest numbers in the array.
 And continue until no numbers remain to be sorted.
It is called a “selection” sort because at every step you search through the rest of the array to select the next lowest number.
An example
Suppose the numbers to sort are [ 5, 8, 3, 4, 6 ]
. We also keep track of where the sorted portion of the array ends, denoted by the 
symbol.
Initially, the sorted portion is empty:


Now we find the lowest number in the array. We do that by scanning through the array from left to right, starting at the 
bar. We find the number 3
.
To put this number into the sorted position, we swap it with the number next to the 
, which is 5
:


The sorted portion is now [ 3 ]
and the rest is [ 8, 5, 4, 6 ]
.
Again, we look for the lowest number, starting from the 
bar. We find 4
and swap it with 8
to get:


With every step, the 
bar moves one position to the right. We again look through the rest of the array and find 5
as the lowest number. There is no need to swap 5
with itself, and we simply move forward:


This process repeats until the array is sorted. Note that everything to the left of the 
bar is always in sorted order and always contains the lowest numbers in the array. Finally, we end up with:


The selection sort is an inplace sort because everything happens in the same array without using additional memory. You can also implement this as a stable sort so that identical elements do not get swapped around relative to each other (note that the version given below is not stable).
The code
Here is an implementation of selection sort in Swift:


Put this code in a playground and test it like so:


A stepbystep explanation of how the code works:
 If the array is empty or only contains a single element, then there is no need to sort.
 Make a copy of the array. This is necessary because we cannot modify the contents of the
array
parameter directly in Swift. Like the Swift’ssort()
function, theselectionSort()
function will return a sorted copy of the original array.  There are two loops inside this function. The outer loop looks at each of the elements in the array in turn; this is what moves the

bar forward.  This is the inner loop. It finds the lowest number in the rest of the array.
 Swap the lowest number with the current array index. The
if
check is necessary because you can’tswap()
an element with itself in Swift.
In summary: For each element of the array, the selection sort swaps positions with the lowest value from the rest of the array. As a result, the array gets sorted from the left to the right. (You can also do it righttoleft, in which case you always look for the largest number in the array. Give that a try!)
Note: The outer loop ends at index
a.count  2
. The very last element will automatically be in the correct position because at that point there are no other smaller elements left.
The source file SelectionSort.swift has a version of this function that uses generics, so you can also use it to sort strings and other data types.
Performance
The selection sort is easy to understand but it performs slow as O(n^2). It is worse than insertion sort but better than bubble sort. Finding the lowest element in the rest of the array is slow, especially since the inner loop will be performed repeatedly.
The Heap sort uses the same principle as selection sort but has a fast method for finding the minimum value in the rest of the array. The heap sort’ performance is O(n log n).
Shell Sort
Shell sort is based on insertion sort as a general way to improve its performance, by breaking the original list into smaller sublists which are then individually sorted using insertion sort.
There is a nice video created at Sapientia University which shows the process as a Hungarian folk dance.
How it works
Instead of comparing elements that are sidebyside and swapping them if they are out of order, the way insertion sort does it, the shell sort algorithm compares elements that are far apart.
The distance between elements is known as the gap. If the elements being compared are in the wrong order, they are swapped across the gap. This eliminates many inbetween copies that are common with insertion sort.
The idea is that by moving the elements over large gaps, the array becomes partially sorted quite quickly. This makes later passes faster because they don’t have to swap so many items anymore.
Once a pass has been completed, the gap is made smaller and a new pass starts. This repeats until the gap has size 1, at which point the algorithm functions just like insertion sort. But since the data is already fairly well sorted by then, the final pass can be very quick.
An example
Suppose we want to sort the array [64, 20, 50, 33, 72, 10, 23, 1, 4]
using shell sort.
We start by dividing the length of the array by 2:


This is the gap size.
We create n
sublists. In each sublist, the items are spaced apart by a gap of size n
. In our example, we need to make four of these sublists. The sublists are sorted by the insertionSort()
function.
That may not have made a whole lot of sense, so let’s take a closer look at what happens.
The first pass is as follows. We have n = 4
, so we make four sublists:


As you can see, each sublist contains only every 4th item from the original array. The items that are not in a sublist are marked with xx
. So the first sublist is [ 64, 72, 4 ]
and the second is [ 20, 10 ]
, and so on. The reason we use this “gap” is so that we don’t have to actually make new arrays. Instead, we interleave them in the original array.
We now call insertionSort()
once on each sublist.
This particular version of insertion sort sorts from the back to the front. Each item in the sublist is compared against the others. If they’re in the wrong order, the value is swapped and travels all the way down until we reach the start of the sublist.
So for sublist 0, we swap 4
with 72
, then swap 4
with 64
. After sorting, this sublist looks like:


The other three sublists after sorting:


The total array looks like this now:


It’s not entirely sorted yet but it’s more sorted than before. This completes the first pass.
In the second pass, we divide the gap size by two:


That means we now create only two sublists:


Each sublist contains every 2nd item. Again, we call insertionSort()
to sort these sublists. The result is:


Note that in each list only two elements were out of place. So the insertion sort is really fast. That’s because we already sorted the array a little in the first pass.
The total array looks like this now:


This completes the second pass. The gap size of the final pass is:


A gap size of 1 means we only have a single sublist, the array itself, and once again we call insertionSort()
to sort it. The final sorted array is:


The performance of shell sort is O(n^2) in most cases or O(n log n) if you get lucky. This algorithm produces an unstable sort; it may change the relative order of elements with equal values.
The gap sequence
The “gap sequence” determines the initial size of the gap and how it is made smaller with each iteration. A good gap sequence is important for shell sort to perform well.
The gap sequence in this implementation is the one from Shell’s original version: the initial value is half the array size and then it is divided by 2 each time. There are other ways to calculate the gap sequence.
Just for fun…
This is an old Commodore 64 BASIC version of shell sort that Matthijs used a long time ago and ported to pretty much every programming language he ever used:


The Code:
Here is an implementation of Shell Sort in Swift:


Fast sorts:
Quicksort
Goal: Sort an array from low to high (or high to low).
Quicksort is one of the most famous algorithms in history. It was invented way back in 1959 by Tony Hoare, at a time when recursion was still a fairly nebulous concept.
Here’s an implementation in Swift that should be easy to understand:


Put this code in a playground and test it like so:


Here’s how it works. When given an array, quicksort()
splits it up into three parts based on a “pivot” variable. Here, the pivot is taken to be the element in the middle of the array (later on you’ll see other ways to choose the pivot).
All the elements less than the pivot go into a new array called less
. All the elements equal to the pivot go into the equal
array. And you guessed it, all elements greater than the pivot go into the third array, greater
. This is why the generic type T
must be Comparable
, so we can compare the elements with <
, ==
, and >
.
Once we have these three arrays, quicksort()
recursively sorts the less
array and the greater
array, then glues those sorted subarrays back together with the equal
array to get the final result.
An example
Let’s walk through the example. The array is initially:


First, we pick the pivot element. That is 8
because it’s in the middle of the array. Now we split the array into the less, equal, and greater parts:


This is a good split because less
and greater
roughly contain the same number of elements. So we’ve picked a good pivot that chopped the array right down the middle.
Note that the less
and greater
arrays aren’t sorted yet, so we call quicksort()
again to sort those two subarrays. That does the exact same thing: pick a pivot and split the subarray into three even smaller parts.
Let’s just take a look at the less
array:


The pivot element is the one in the middle, 1
. (You could also have picked 2
, it doesn’t matter.) Again, we create three subarrays around the pivot:


We’re not done yet and quicksort()
again is called recursively on the less
and greater
arrays. Let’s look at less
again:


As pivot we pick 1
. Now the subarrays are:


The less
array is empty because there was no value smaller than 1
; the other arrays contain a single element each. That means we’re done at this level of the recursion, and we go back up to sort the previous greater
array.
That greater
array was:


This works just the same way as before: we pick the middle element 2
as the pivot and fill up the subarrays:


Note that here it would have been better to pick 3
as the pivot – we would have been done sooner. But now we have to recurse into the greater
array again to make sure it is sorted. This is why picking a good pivot is important. When you pick too many “bad” pivots, quicksort actually becomes really slow. More on that below.
When we partition the greater
subarray, we find:


And now we’re done at this level of the recursion because we can’t split up the arrays any further.
This process repeats until all the subarrays have been sorted. In a picture:
Now if you read the colored boxes from left to right, you get the sorted array:


This shows that 8
was a good initial pivot because it appears in the middle of the sorted array too.
I hope this makes the basic principle clear of how quicksort works. Unfortunately, this version of quicksort isn’t very quick, because we filter()
the same array three times. There are more clever ways to split up the array.
Partitioning
Dividing the array around the pivot is called partitioning and there are a few different partitioning schemes.
If the array is,


and we choose the middle element 8
as a pivot then after partitioning the array will look like this:


The key thing to realize is that after partitioning the pivot element is in its final sorted place already. The rest of the numbers are not sorted yet, they are simply partitioned around the pivot value. Quicksort partitions the array many times over, until all the values are in their final places.
There is no guarantee that partitioning keeps the elements in the same relative order, so after partitioning around pivot 8
you could also end up with something like this:


The only guarantee is that to the left of the pivot are all the smaller elements and to the right are all the larger elements. Because partitioning can change the original order of equal elements, quicksort does not produce a “stable” sort (unlike merge sort, for example). Most of the time that’s not a big deal.
Lomuto’s partitioning scheme
In the first example of quicksort I showed you, partitioning was done by calling Swift’s filter()
function three times. That is not very efficient. So let’s look at a smarter partitioning algorithm that works in place, i.e. by modifying the original array.
Here’s an implementation of Lomuto’s partitioning scheme in Swift:


To test this in a playground, do:


Note that list
needs to be a var
because partitionLomuto()
directly changes the contents of the array (it is passed as an inout
parameter). That is much more efficient than allocating a new array object.
The low
and high
parameters are necessary because when this is used inside quicksort, you don’t always want to (re)partition the entire array, only a limited range that becomes smaller and smaller.
Previously we used the middle array element as the pivot but it’s important to realize that the Lomuto algorithm always uses the last element, a[high]
, for the pivot. Because we’ve been pivoting around 8
all this time, I swapped the positions of 8
and 26
in the example so that 8
is at the end of the array and is used as the pivot value here too.
After partitioning, the array looks like this:


The variable p
contains the return value of the call to partitionLomuto()
and is 7. This is the index of the pivot element in the new array (marked with a star).
The left partition goes from 0 to p1
and is [ 0, 3, 2, 1, 5, 8, 1 ]
. The right partition goes from p+1
to the end, and is [ 9, 10, 14, 26, 27 ]
(the fact that the right partition is already sorted is a coincidence).
You may notice something interesting… The value 8
occurs more than once in the array. One of those 8
s did not end up neatly in the middle but somewhere in the left partition. That’s a small downside of the Lomuto algorithm as it makes quicksort slower if there are a lot of duplicate elements.
So how does the Lomuto algorithm actually work? The magic happens in the for
loop. This loop divides the array into four regions:
a[low...i]
contains all values <= pivota[i+1...j1]
contains all values > pivota[j...high1]
are values we haven’t looked at yeta[high]
is the pivot value
In ASCII art the array is divided up like this:


The loop looks at each element from low
to high1
in turn. If the value of the current element is less than or equal to the pivot, it is moved into the first region using a swap.
Note: In Swift, the notation
(x, y) = (y, x)
is a convenient way to perform a swap between the values ofx
andy
. You can also writeswap(&x, &y)
.
After the loop is over, the pivot is still the last element in the array. So we swap it with the first element that is greater than the pivot. Now the pivot sits between the <= and > regions and the array is properly partitioned.
Let’s step through the example. The array we’re starting with is:


Initially, the “not looked at” region stretches from index 0 to 11. The pivot is at index 12. The “values <= pivot” and “values > pivot” regions are empty, because we haven’t looked at any values yet.
Look at the first value, 10
. Is this smaller than the pivot? No, skip to the next element.


Now the “not looked at” region goes from index 1 to 11, the “values > pivot” region contains the number 10
, and “values <= pivot” is still empty.
Look at the second value, 0
. Is this smaller than the pivot? Yes, so swap 10
with 0
and move i
ahead by one.


Now “not looked at” goes from index 2 to 11, “values > pivot” still contains 10
, and “values <= pivot” contains the number 0
.
Look at the third value, 3
. This is smaller than the pivot, so swap it with 10
to get:


The “values <= pivot” region is now [ 0, 3 ]
. Let’s do one more… 9
is greater than the pivot, so simply skip ahead:


Now the “values > pivot” region contains [ 10, 9 ]
. If we keep going this way, then eventually we end up with:


The final thing to do is to put the pivot into place by swapping a[i]
with a[high]
:


And we return i
, the index of the pivot element.
Note: If you’re still not entirely clear on how the algorithm works, I suggest you play with this in the playground to see exactly how the loop creates these four regions.
Let’s use this partitioning scheme to build quicksort. Here’s the code:


This is now super simple. We first call partitionLomuto()
to reorder the array around the pivot (which is always the last element from the array). And then we call quicksortLomuto()
recursively to sort the left and right partitions.
Try it out:


Lomuto’s isn’t the only partitioning scheme but it’s probably the easiest to understand. It’s not as efficient as Hoare’s scheme, which requires fewer swap operations.
Hoare’s partitioning scheme
This partitioning scheme is by Hoare, the inventor of quicksort.
Here is the code:


To test this in a playground, do:


Note that with Hoare’s scheme, the pivot is always expected to be the first element in the array, a[low]
. Again, we’re using 8
as the pivot element.
The result is:


Note that this time the pivot isn’t in the middle at all. Unlike with Lomuto’s scheme, the return value is not necessarily the index of the pivot element in the new array.
Instead, the array is partitioned into the regions [low...p]
and [p+1...high]
. Here, the return value p
is 6, so the two partitions are [ 1, 0, 3, 8, 2, 5, 1 ]
and [ 27, 10, 14, 9, 8, 26 ]
.
The pivot is placed somewhere inside one of the two partitions, but the algorithm doesn’t tell you which one or where. If the pivot value occurs more than once, then some instances may appear in the left partition and others may appear in the right partition.
Because of these differences, the implementation of Hoare’s quicksort is slightly different:


I’ll leave it as an exercise for the reader to figure out exactly how Hoare’s partitioning scheme works. :)
Picking a good pivot
Lomuto’s partitioning scheme always chooses the last array element for the pivot. Hoare’s scheme uses the first element. But there is no guarantee that these pivots are any good.
Here is what happens when you pick a bad value for the pivot. Let’s say the array is,


and we’re using Lomuto’s scheme. The pivot is the last element, 1
. After pivoting, we have the following arrays:


Now recursively partition the “greater than” subarray and get:


And again:


And so on…
That’s no good, because this pretty much reduces quicksort to the much slower insertion sort. For quicksort to be efficient, it needs to split the array into roughly two halves.
The optimal pivot for this example would have been 4
, so we’d get:


You might think this means we should always choose the middle element rather than the first or the last, but imagine what happens in the following situation:


Now the middle element is 1
and that gives the same lousy results as in the previous example.
Ideally, the pivot is the median element of the array that you’re partitioning, i.e. the element that sits in the middle of the sorted array. Of course, you won’t know what the median is until after you’ve sorted the array, so this is a bit of a chickenandegg problem. However, there are some tricks to choose good, if not ideal, pivots.
One trick is “medianofthree”, where you find the median of the first, middle, and last element in this subarray. In theory that often gives a good approximation of the true median.
Another common solution is to choose the pivot randomly. Sometimes this may result in choosing a suboptimal pivot but on average this gives very good results.
Here is how you can do quicksort with a randomly chosen pivot:


There are two important differences with before:
 The
random(min:max:)
function returns an integer in the rangemin...max
, inclusive. This is our pivot index.  Because the Lomuto scheme expects
a[high]
to be the pivot entry, we swapa[pivotIndex]
witha[high]
to put the pivot element at the end before callingpartitionLomuto()
.
It may seem strange to use random numbers in something like a sorting function, but it is necessary to make quicksort behave efficiently under all circumstances. With bad pivots, the performance of quicksort can be quite horrible, O(n^2). But if you choose good pivots on average, for example by using a random number generator, the expected running time becomes O(n log n), which is as good as sorting algorithms get.
Dutch national flag 🇳🇱 partitioning
But there are more improvements to make! In the first example of quicksort I showed you, we ended up with an array that was partitioned like this:


But as you’ve seen with the Lomuto partitioning scheme, if the pivot occurs more than once the duplicates end up in the left half. And with Hoare’s scheme the pivot can be all over the place. The solution to this is “Dutch national flag” partitioning, named after the fact that the Dutch flag has three bands just like we want to have three partitions.
The code for this scheme is:


This works very similarly to the Lomuto scheme, except that the loop partitions the array into four (possibly empty) regions:
[low ... smaller1]
contains all values < pivot[smaller ... equal1]
contains all values == pivot[equal ... larger]
contains all values > pivot[larger ... high]
are values we haven’t looked at yet
Note that this doesn’t assume the pivot is in a[high]
. Instead, you have to pass in the index of the element you wish to use as a pivot.
An example of how to use it:


Just for fun, we’re giving it the index of the other 8
this time. The result is:


Notice how the two 8
s are in the middle now. The return value from partitionDutchFlag()
is a tuple, (6, 7)
. This is the range that contains the pivot value(s).
Here is how you would use it in quicksort:


Using Dutch flag partitioning makes for a more efficient quicksort if the array contains many duplicate elements. (And I’m not just saying that because I’m Dutch!)
Note: The above implementation of
partitionDutchFlag()
uses a customswap()
routine for swapping the contents of two array elements. Unlike Swift’s ownswap()
, this doesn’t give an error when the two indices refer to the same array element. See Quicksort.swift for the code.
Merge Sort
This topic has been tutorialized here
Goal: Sort an array from low to high (or high to low)
Invented in 1945 by John von Neumann, mergesort is an efficient algorithm with a best, worst, and average time complexity of O(n log n).
The mergesort algorithm uses the divide and conquer approach which is to divide a big problem into smaller problems and solve them. I think of the mergesort algorithm as split first and merge after.
Assume you need to sort an array of n numbers in the right order. The mergesort algorithm works as follows:
 Put the numbers in an unsorted pile.
 Split the pile into two. Now, you have two unsorted piles of numbers.
 Keep splitting the resulting piles until you cannot split anymore. In the end, you will have n piles with one number in each pile.
 Begin to merge the piles together by pairing them sequentially. During each merge, put the contents in sorted order. This is fairly easy because each individual pile is already sorted.
An example
Splitting
Assume you are given an array of n numbers as[2, 1, 5, 4, 9]
. This is an unsorted pile. The goal is to keep splitting the pile until you cannot split anymore.
First, split the array into two halves: [2, 1]
and [5, 4, 9]
. Can you keep splitting them? Yes, you can!
Focus on the left pile. Split[2, 1]
into [2]
and [1]
. Can you keep splitting them? No. Time to check the other pile.
Split [5, 4, 9]
into [5]
and [4, 9]
. Unsurprisingly, [5]
cannot be split anymore, but [4, 9]
can be split into [4]
and [9]
.
The splitting process ends with the following piles: [2]
[1]
[5]
[4]
[9]
. Notice that each pile consists of just one element.
Merging
Now that you have split the array, you should merge the piles together while sorting them. Remember, the idea is to solve many small problems rather than a big one. For each merge iteration, you must be concerned at merging one pile with another.
Given the piles [2]
[1]
[5]
[4]
[9]
, the first pass will result in [1, 2]
and [4, 5]
and [9]
. Since [9]
is the odd one out, you cannot merge it with anything during this pass.
The next pass will merge [1, 2]
and [4, 5]
together. This results in [1, 2, 4, 5]
, with the [9]
left out again because it is the odd one out.
You are left with only two piles [1, 2, 4, 5]
and [9]
, finally gets its chance to merge, resulting in the sorted array as [1, 2, 4, 5, 9]
.
Topdown implementation
Here’s what merge sort may look like in Swift:


A stepbystep explanation of how the code works:
 If the array is empty or contains a single element, there is no way to split it into smaller pieces. You must just return the array.
 Find the middle index.
 Using the middle index from the previous step, recursively split the left side of the array.
 Also, recursively split the right side of the array.
 Finally, merge all the values together, making sure that it is always sorted.
Here’s the merging algorithm:


This method may look scary, but it is quite straightforward:
 You need two indexes to keep track of your progress for the two arrays while merging.
 This is the merged array. It is empty right now, but you will build it up in subsequent steps by appending elements from the other arrays. Since you already know number of elements that will end up in this array, you reserve capacity to avoid reallocation overhead later.
 This whileloop will compare the elements from the left and right sides and append them into the
orderedPile
while making sure that the result stays in order.  If control exits from the previous whileloop, it means that either the
leftPile
or therightPile
has its contents completely merged into theorderedPile
. At this point, you no longer need to do comparisons. Just append the rest of the contents of the other array until there is no more to append.
As an example of how merge()
works, suppose that we have the following piles: leftPile = [1, 7, 8]
and rightPile = [3, 6, 9]
. Note that each of these piles is individually sorted already – that is always true with merge sort. These are merged into one larger sorted pile in the following steps:


The left index, here represented as l
, points at the first item from the left pile, 1
. The right index, r
, points at 3
. Therefore, the first item we add to orderedPile
is 1
. We also move the left index l
to the next item.


Now l
points at 7
but r
is still at 3
. We add the smallest item to the ordered pile, so that is 3
. The situation is now:


This process repeats. At each step, we pick the smallest item from either the leftPile
or the rightPile
and add the item into the orderedPile
:


Now, there are no more items in the left pile. We simply add the remaining items from the right pile, and we are done. The merged pile is [ 1, 3, 6, 7, 8, 9 ]
.
Notice that, this algorithm is very simple: it moves from lefttoright through the two piles and at every step picks the smallest item. This works because we guarantee that each of the piles is already sorted.
Here is a dynamic implementation process
Bottomup implementation
The implementation of the mergesort algorithm you have seen so far is called the “topdown” approach because it first splits the array into smaller piles and then merges them. When sorting an array (as opposed to, say, a linked list) you can actually skip the splitting step and immediately start merging the individual array elements. This is called the “bottomup” approach.
Time to step up the game a little. :) Here is a complete bottomup implementation in Swift:


It looks a lot more intimidating than the topdown version, but notice that the main body includes the same three while
loops from merge()
.
Notable points:
 The Mergesort algorithm needs a temporary working array because you cannot merge the left and right piles and at the same time overwrite their contents. Because allocating a new array for each merge is wasteful, we are using two working arrays, and we will switch between them using the value of
d
, which is either 0 or 1. The arrayz[d]
is used for reading, andz[1  d]
is used for writing. This is called doublebuffering.  Conceptually, the bottomup version works the same way as the topdown version. First, it merges small piles of one element each, then it merges piles of two elements each, then piles of four elements each, and so on. The size of the pile is given by
width
. Initially,width
is1
but at the end of each loop iteration, we multiply it by two, so this outer loop determines the size of the piles being merged, and the subarrays to merge become larger in each step.  The inner loop steps through the piles and merges each pair of piles into a larger one. The result is written in the array given by
z[1  d]
.  This is the same logic as in the topdown version. The main difference is that we’re using doublebuffering, so values are read from
z[d]
and written intoz[1  d]
. It also uses anisOrderedBefore
function to compare the elements rather than just<
, so this mergesort algorithm is generic, and you can use it to sort any kind of object you want.  At this point, the piles of size
width
from arrayz[d]
have been merged into larger piles of sizewidth * 2
in arrayz[1  d]
. Here, we swap the active array, so that in the next step we’ll read from the new piles we have just created.
This function is generic, so you can use it to sort any type you desire, as long as you provide a proper isOrderedBefore
closure to compare the elements.
Example of how to use it:


Performance
The speed of the mergesort algorithm is dependent on the size of the array it needs to sort. The larger the array, the more work it needs to do.
Whether or not the initial array is sorted already does not affect the speed of the mergesort algorithm since you will be doing the same amount splits and comparisons regardless of the initial order of the elements.
Therefore, the time complexity for the best, worst, and average case will always be O(n log n).
A disadvantage of the mergesort algorithm is that it needs a temporary “working” array equal in size to the array being sorted. It is not an inplace sort, unlike for example quicksort.
Most implementations of the mergesort algorithm produce a stable sort. This means that array elements that have identical sort keys will stay in the same order relative to each other after sorting. This is not important for simple values such as numbers or strings, but it can be an issue when sorting more complex objects.
Heap Sort
Sorts an array from low to high using a heap.
A heap is a partially sorted binary tree that is stored inside an array. The heap sort algorithm takes advantage of the structure of the heap to perform a fast sort.
To sort from lowest to highest, heap sort first converts the unsorted array to a maxheap, so that the first element in the array is the largest.
Let’s say the array to sort is:


This is first turned into a maxheap that looks like this:
The heap’s internal array is then:


That’s hardly what you’d call sorted! But now the sorting process starts: we swap the first element (index 0) with the last one at index n1, to get:


Now the new root node, 4
, will be smaller than its children, so we fix up the maxheap up to element n2 using the shift down or “heapify” procedure. After repairing the heap, the new root is now the secondlargest item in the array:


Important: When we fix the heap, we ignore the last item at index n1. That now contains the array’s maximum value, so it is in its final sorted place already. The 
bar indicates where the sorted portion of the array begins. We’ll leave that part of the array alone from now on.
Again, we swap the first element with the last one (this time at index n2):


And fix up the heap to make it valid maxheap again:


As you can see, the largest items are making their way to the back. We repeat this process until we arrive at the root node and then the whole array is sorted.
Note: This process is very similar to selection sort, which repeatedly looks for the minimum item in the remainder of the array. Extracting the minimum or maximum value is what heaps are good at.
Performance of heap sort is O(n lg n) in best, worst, and average case. Because we modify the array directly, heap sort can be performed inplace. But it is not a stable sort: the relative order of identical elements is not preserved.
Here’s how you can implement heap sort in Swift:


This adds a sort()
function to our heap implementation. To use it, you would do something like this:


Because we need a maxheap to sort from lowtohigh, you need to give Heap
the reverse of the sort function. To sort <
, the Heap
object must be created with >
as the sort function. In other words, sorting from lowtohigh creates a maxheap and turns it into a minheap.
We can write a handy helper function for that:


Hybrid sorts:
IntroSort
Goal: Sort an array from low to high (or high to low).
IntroSort is the algorithm used by swift to sort a collection. Introsort is an hybrid algorithm invented by David Musser in 1993 with the purpose of giving a generic sorting algorithm for the C++ standard library. The classic implementation of introsort expect a recursive Quicksort with fallback to Heapsort in case the recursion depth level reached a certain max. The maximum depends on the number of elements in the collection and it is usually 2 log(n). The reason behind this “fallback” is that if Quicksort was not able to get the solution after 2 log(n) recursions for a branch, probably it hit its worst case and it is degrading to complexity O( n^2 ). To optimise even further this algorithm, the swift implementation introduce an extra step in each recursion where the partition is sorted using InsertionSort if the count of the partition is less than 20.
The number 20 is an empiric number obtained observing the behaviour of InsertionSort with lists of this size.
Here’s an implementation in pseudocode:


An example
Let’s walk through the example. The array is initially:


For this example let’s assume that maxDepth
is 2 and that the size of the partition for the insertionSort to kick in is 5
The first iteration of introsort begins by attempting to use insertionSort. The collection has 13 elements, so it tries to do heapsort instead. The condition for heapsort to occur is if maxdepth == 0
evaluates true. Since maxdepth
is currently 2for the first iteration, introsort will default to quicksort.
The partition
method picks the first element, the median and the last, it sorts them and uses the new median as pivot.


Our array is now


10 is the pivot. After the choice of the pivot, the partition
method swaps elements to get all the elements less than pivot on the left, and all the elements more or equal than pivot on the right.


Because of the swaps, the index of of pivot is now changed and returned. The next step of introsort is to call recursively itself for the two sub arrays:


maxDepth: 1, branch: less


The count of the array is still more than 5 so we don’t meet yet the conditions for insertion sort to kick in. At this iteration maxDepth is decreased by one but it is still more than zero, so heapsort will not act.
Just like in the previous iteration quicksort wins and the partition
method choses a pivot and sorts the elemets less than pivot on the left and the elements more or equeal than pivot on the right.


maxDepth: 0, branch: less


Just like before, introsort is recursively executed for less
and greater. This time less
has a count more than 5 so it will not be sorted with insertion sort, but the maxDepth decreased again by 1 is now 0 and heapsort takes over sorting the array.


maxDepth: 0, branch: greater


following greater in this recursion, the count of elements is 3, which is less than 5, so this partition is sorted using insertionSort.


back to maxDepth = 1, branch: greater


At this point the original array has mutated to be


now the less
partition is sorted and since the count of the greater
partition is 3 it will be sorted with insertion sort [ 14, 26, 27 ]
The array is now successfully sorted


Specialpurpose sorts:
Counting Sort
Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key values, and using arithmetic on those counts to determine the positions of each key value in the output sequence.
Example
To understand the algorithm let’s walk through a small example.
Consider the array: [ 10, 9, 8, 7, 1, 2, 7, 3 ]
Step 1:
The first step is to count the total number of occurrences for each item in the array. The output for the first step would be a new array that looks as follows:


Here is the code to accomplish this:


Step 2:
In this step the algorithm tries to determine the number of elements that are placed before each element. Since, you already know the total occurrences for each element you can use this information to your advantage. The way it works is to sum up the previous counts and store them at each index.
The count array would be as follows:


The code for step 2 is:


Step 3:
This is the last step in the algorithm. Each element in the original array is placed at the position defined by the output of step 2. For example, the number 10 would be placed at an index of 7 in the output array. Also, as you place the elements you need to reduce the count by 1 as those many elements are reduced from the array.
The final output would be:


Here is the code for this final step:


Performance
The algorithm uses simple loops to sort a collection. Hence, the time to run the entire algorithm is O(n+k) where O(n)represents the loops that are required to initialize the output arrays and O(k) is the loop required to create the count array.
The algorithm uses arrays of length n + 1 and n, so the total space required is O(2n). Hence for collections where the keys are scattered in a dense area along the number line it can be space efficient.
Radix Sort
Radix sort is a sorting algorithm that takes as input an array of integers and uses a sorting subroutine( that is often another efficient sorting algorith) to sort the integers by their radix, or rather their digit. Counting Sort, and Bucket Sort are often times used as the subroutine for Radix Sort.
Example
 Input Array: [170, 45, 75, 90, 802, 24, 2, 66]
 Output Array (Sorted): [2, 24, 45, 66, 75, 90, 170, 802]
Step 1:
The first step in this algorithm is to define the digit or rather the “base” or radix that we will use to sort. For this example we will let radix = 10, since the integers we are working with in the example are of base 10.
Step 2:
The next step is to simply iterate n times (where n is the number of digits in the largest integer in the input array), and upon each iteration perform a sorting subroutine on the current digit in question.
Algorithm in Action
Let’s take a look at our example input array.
The largest integer in our array is 802, and it has three digits (ones, tens, hundreds). So our algorithm will iterate three times whilst performing some sorting algorithm on the digits of each integer.
 Iteration 1: 170, 90, 802, 2, 24, 45, 75, 66
 Iteration 2: 802, 2, 24, 45, 66, 170, 75, 90
 Iteration 3: 2, 24, 45, 66, 75, 90, 170, 802
Topological Sort
Topological sort is an algorithm that orders a directed graph such that for each directed edge u→v, vertex u comes before vertex v.
In other words, a topological sort places the vertices of a directed acyclic graph on a line so that all directed edges go from left to right.
Consider the graph in the following example:
This graph has two possible topological sorts:
The topological orderings are S, V, W, T, X and S, W, V, T, X. Notice how the arrows all go from left to right.
The following is not a valid topological sort for this graph, since X and T cannot happen before V:
Where is this used?
Let’s consider that you want to learn all the algorithms and data structures from the Swift Algorithm Club. This might seem daunting at first but we can use topological sort to get things organized.
Since you’re learning about topological sort, let’s take this topic as an example. What else do you need to learn first before you can fully understand topological sort? Well, topological sort uses depthfirst search as well as a stack. But before you can learn about the depthfirst search algorithm, you need to know what a graph is, and it helps to know what a tree is. In turn, graphs and trees use the idea of linking objects together, so you may need to read up on that first. And so on…
If we were to represent these objectives in the form of a graph it would look as follows:
If we consider each algorithm to be a vertex in the graph you can clearly see the dependencies between them. To learn something you might have to know something else first. This is exactly what topological sort is used for – it will sort things out so that you know what to do first.
How does it work?
Step 1: Find all vertices that have indegree of 0
The indegree of a vertex is the number of edges pointing at that vertex. Vertices with no incoming edges have an indegree of 0. These vertices are the starting points for the topological sort.
In the context of the previous example, these starting vertices represent algorithms and data structures that don’t have any prerequisites; you don’t need to learn anything else first, hence the sort starts with them.
Step 2: Traverse the graph with depthfirst search
Depthfirst search is an algorithm that starts traversing the graph from a certain vertex and explores as far as possible along each branch before backtracking. To find out more about depthfirst search, please take a look at the detailed explanation.
We perform a depthfirst search on each vertex with indegree 0. This tells us which vertices are connected to each of these starting vertices.
Step 3: Remember all visited vertices
As we perform the depthfirst search, we maintain a list of all the vertices that have been visited. This is to avoid visiting the same vertex twice.
Step 4: Put it all together
The last step of the sort is to combine the results of the different depthfirst searches and put the vertices in a sorted list.
Example
Consider the following graph:
Step 1: The vertices with 0 indegree are: 3, 7, 5. These are our starting vertices.
Step 2: Perform depthfirst search for each starting vertex, without remembering vertices that have already been visited:


Step 3: Filter out the vertices already visited in each previous search:


Step 4: Combine the results of these three depthfirst searches. The final sorted order is 5, 7, 11, 2, 3, 10, 8, 9. (Important: we need to add the results of each subsequent search to the front of the sorted list.)
The result of the topological sort looks like this:
Note: This is not the only possible topological sort for this graph. For example, other valid solutions are 3, 7, 5, 10, 8, 11, 9, 2 and 3, 7, 5, 8, 11, 2, 9, 10. Any order where all the arrows are going from left to right will do.
The code
Here is how you could implement topological sort in Swift (see also TopologicalSort1.swift):


Some remarks:
 Find the indegree of each vertex and put all the vertices with indegree 0 in the
startNodes
array. In this graph implementation, vertices are called “nodes”. Both terms are used interchangeably by people who write graph code.  The
visited
array keeps track of whether we’ve already seen a vertex during the depthfirst search. Initially, we set all elements tofalse
.  For each of the vertices in the
startNodes
array, perform a depthfirst search. This returns an array of sortedNode
objects. We prepend that array to our ownresult
array.  The
result
array contains all the vertices in topologically sorted order.
Note: For a slightly different implementation of topological sort using depthfirst search, see TopologicalSort3.swift. This uses a stack and does not require you to find all vertices with indegree 0 first.
Kahn’s algorithm
Even though depthfirst search is the typical way to perform a topological sort, there is another algorithm that also does the job.
 Find out what the indegree is of every vertex.
 Put all the vertices that have no predecessors in a new array called
leaders
. These vertices have indegree 0 and therefore do not depend on any other vertices.  Go through this list of leaders and remove them onebyone from the graph. We don’t actually modify the graph, we just decrement the indegree of the vertices they point to. That has the same effect.
 Look at the (former) immediate neighbor vertices of each leader. If any of them now have an indegree of 0, then they no longer have any predecessors themselves. We’ll add those vertices to the
leaders
array too.  This repeats until there are no more vertices left to look at. At this point, the
leaders
array contains all the vertices in sorted order.
This is an O(n + m) algorithm where n is the number of vertices and m is the number of edges. You can see the implementation in TopologicalSort2.swift.
Bad sorting algorithms (don’t use these!):
Bubble Sort
Bubble sort is a sorting algorithm that is implemented by starting in the beginning of the array and swapping the first two elements only if the first element is greater than the second element. This comparison is then moved onto the next pair and so on and so forth. This is done until the array is completely sorted. The smaller items slowly “bubble” up to the beginning of the array. Sometimes this algorithm is refered as Sinking sort, due to the larger, or heavier elements sinking to the end of the array.
Runtime:
 Average: O(N^2)
 Worst: O(N^2)
Memory:
 O(1)
Implementation:
The implementation will not be shown as the average and worst runtimes show that this is a very inefficient algorithm. However, having a grasp of the concept will help you understand the basics of simple sorting algorithms.
Bubble sort is a very simple sorting algorithm, it consists in comparing pairs of adjacent elements in the array, if the first element is larger, swap them, otherwise, you do nothing and go for the next comparison. This is accomplished by looking through the array n
times, n
being the amount of elements in the array.
Example
Let us take the array [5, 1, 4, 2, 8]
, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.
First Pass
[ 5 1 4 2 8 ] > [ 1 5 4 2 8 ], Here, algorithm compares the first two elements, and swaps since 5 > 1.
[ 1 5 4 2 8 ] > [ 1 4 5 2 8 ], Swap since 5 > 4
[ 1 4 5 2 8 ] > [ 1 4 2 5 8 ], Swap since 5 > 2
[ 1 4 2 5 8 ] > [ 1 4 2 5 8 ], Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass
[ 1 4 2 5 8 ] > [ 1 4 2 5 8 ]
[ 1 4 2 5 8 ] > [ 1 2 4 5 8 ], Swap since 4 > 2
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ] Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
This is the same for the forth and fifth passes.
Code


Optimization
The bubble sort algorithm can be easily optimized by observing that the nth
pass finds the nth
largest element and puts it into its final place. So, the inner loop can avoid looking at the last n1
items when running for the nth
time:


The only change made was on the second line, changing the interval from 1..<array.count
to 1..<array.count  i
, effectively cutting the number of comparisons by half.
The ordering with the optimized code would look something like this for the array [5, 1, 4, 2, 8]
:
First Pass
[ 5 1 4 2 8 ] > [ 1 5 4 2 8 ], Swaps since 5 > 1
[ 1 5 4 2 8 ] > [ 1 4 5 2 8 ], Swap since 5 > 4
[ 1 4 5 2 8 ] > [ 1 4 2 5 8 ], Swap since 5 > 2
[ 1 4 2 5 8 ] > [ 1 4 2 5 8 ], Now, since these elements are already in order (8 > 5), algorithm does not swap them.
by the end of the first pass, the last element is guaranteed to be the largest
Second Pass
[ 1 4 2 5 8 ] > [ 1 4 2 5 8 ]
[ 1 4 2 5 8 ] > [ 1 2 4 5 8 ], Swap since 4 > 2
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ], As the first loop has occured once, the inner loop stops here, not comparing 5 with 8
Third Pass
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ] again, stoping one comparison short
Fourth Pass
[ 1 2 4 5 8 ] > [ 1 2 4 5 8 ]
There is no Fifth pass
Conclusion
Even with the proposed optimizations, this is still a terribly inefficient sorting algorithm. A good alternative is Merge Sort, that not only is better performing, has a similar degree of dificulty to implement.
Slow Sort
Goal: Sort an array of numbers from low to high (or high to low).
You are given an array of numbers and need to put them in the right order. The insertion sort algorithm works as follows:
We can decompose the problem of sorting n numbers in ascending order into
 find the maximum of the numbers
 find the maximum of the first n/2 elements
 find the maximum of the remaining n/2 elements
 find the largest of those two maxima
 sorting the remaining ones
The code
Here is an implementation of slow sort in Swift:


Performance
WORST!
See also
Slow Sort explanation in the Internet