Several sorting algorithms

just several sorting algorithms. Expand reading: Wikipedia
zan

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.
  • Non-comparative 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 non-comparative 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

insertionSort

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.

In-place 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 in-place, 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:

1
[| 8, 3, 5, 4, 6 ]

This shows that the sorted portion is empty and the pile starts at 8.

After processing the first number, we have:

1
[ 8 | 3, 5, 4, 6 ]

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:

1
2
3
4
5
6
[| 8, 3, 5, 4, 6 ]
[ 8 | 3, 5, 4, 6 ]
[ 3, 8 | 5, 4, 6 ]
[ 3, 5, 8 | 4, 6 ]
[ 3, 4, 5, 8 | 6 ]
[ 3, 4, 5, 6, 8 |]

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 top-most 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:

1
[ 3, 5, 8 | 4, 6 ]

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.

1
2
[ 3, 5, 8, 4 | 6 ]
^

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

1
2
3
[ 3, 5, 4, 8 | 6 ]
<-->
swapped

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

1
2
3
[ 3, 4, 5, 8 | 6 ]
<-->
swapped

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:

1
2
3
4
5
6
7
8
9
10
11
func insertionSort(_ array: [Int]) -> [Int] {
var a = array // 1
for x in 1..<a.count { // 2
var y = x
while y > 0 && a[y] < a[y - 1] { // 3
a.swapAt(y - 1, y)
y -= 1
}
}
return a
}

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

1
2
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)

Here is how the code works.

  1. Make a copy of the array. This is necessary because we cannot modify the contents of the array parameter directly. Like Swift’s own sort(), the insertionSort() function will return a sorted copy of the original array.
  2. 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 top-most 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 to x – is always sorted. The rest, from index x until the last element, is the unsorted pile.
  3. 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:

1
2
3
4
5
6
7
[ 3, 5, 8, 4 | 6 ]
<-->
swap
[ 3, 5, 4, 8 | 6 ]
<-->
swap

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.

1
2
3
4
5
6
7
8
9
10
11
[ 3, 5, 8, 4 | 6 ] remember 4
*
[ 3, 5, 8, 8 | 6 ] shift 8 to the right
--->
[ 3, 5, 5, 8 | 6 ] shift 5 to the right
--->
[ 3, 4, 5, 8 | 6 ] copy 4 into place
*

In code that looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
func insertionSort(_ array: [Int]) -> [Int] {
var a = array
for x in 1..<a.count {
var y = x
let temp = a[y]
while y > 0 && temp < a[y - 1] {
a[y] = a[y - 1] // 1
y -= 1
}
a[y] = temp // 2
}
return a
}

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 user-supplied function (or closure) to perform the less-than comparison. This only requires two changes to the code.

The function signature becomes:

1
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {

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 built-in sort() function does.

The only other change is in the inner loop, which now becomes:

1
while y > 0 && isOrderedBefore(temp, a[y - 1]) {

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:

1
2
3
let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)

The < and > determine the sort order, low-to-high and high-to-low, respectively.

Of course, you can also sort other things such as strings,

1
2
let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)

or even more complex objects:

1
2
let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }

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 worst-case 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 built-in 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

selectionSort

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.

1
[ ...sorted numbers... | ...unsorted numbers... ]

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:

1
[| 5, 8, 3, 4, 6 ]

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:

1
2
[ 3 | 8, 5, 4, 6 ]
* *

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:

1
2
[ 3, 4 | 5, 8, 6 ]
* *

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:

1
2
[ 3, 4, 5 | 8, 6 ]
*

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:

1
[ 3, 4, 5, 6, 8 |]

The selection sort is an in-place 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func selectionSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
var a = array // 2
for x in 0 ..< a.count - 1 { // 3
var lowest = x
for y in x + 1 ..< a.count { // 4
if a[y] < a[lowest] {
lowest = y
}
}
if x != lowest { // 5
a.swapAt(x, lowest)
}
}
return a
}

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

1
2
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list)

A step-by-step explanation of how the code works:

  1. If the array is empty or only contains a single element, then there is no need to sort.
  2. 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’s sort() function, the selectionSort() function will return a sorted copy of the original array.
  3. 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.
  4. This is the inner loop. It finds the lowest number in the rest of the array.
  5. Swap the lowest number with the current array index. The if check is necessary because you can’t swap() 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 right-to-left, 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

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 side-by-side 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 in-between 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:

1
n = floor(9/2) = 4

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:

1
2
3
4
sublist 0: [ 64, xx, xx, xx, 72, xx, xx, xx, 4 ]
sublist 1: [ xx, 20, xx, xx, xx, 10, xx, xx, xx ]
sublist 2: [ xx, xx, 50, xx, xx, xx, 23, xx, xx ]
sublist 3: [ xx, xx, xx, 33, xx, xx, xx, -1, xx ]

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:

1
sublist 0: [ 4, xx, xx, xx, 64, xx, xx, xx, 72 ]

The other three sublists after sorting:

1
2
3
sublist 1: [ xx, 10, xx, xx, xx, 20, xx, xx, xx ]
sublist 2: [ xx, xx, 23, xx, xx, xx, 50, xx, xx ]
sublist 3: [ xx, xx, xx, -1, xx, xx, xx, 33, xx ]

The total array looks like this now:

1
[ 4, 10, 23, -1, 64, 20, 50, 33, 72 ]

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:

1
n = floor(4/2) = 2

That means we now create only two sublists:

1
2
sublist 0: [ 4, xx, 23, xx, 64, xx, 50, xx, 72 ]
sublist 1: [ xx, 10, xx, -1, xx, 20, xx, 33, xx ]

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

1
2
sublist 0: [ 4, xx, 23, xx, 50, xx, 64, xx, 72 ]
sublist 1: [ xx, -1, xx, 10, xx, 20, xx, 33, xx ]

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:

1
[ 4, -1, 23, 10, 50, 20, 64, 33, 72 ]

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

1
n = floor(2/2) = 1

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:

1
[ -1, 4, 10, 20, 23, 33, 50, 64, 72 ]

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
61200 REM S is the array to be sorted
61205 REM AS is the number of elements in S
61210 W1=AS
61220 IF W1<=0 THEN 61310
61230 W1=INT(W1/2): W2=AS-W1
61240 V=0
61250 FOR N1=0 TO W2-1
61260 W3=N1+W1
61270 IF S(N1)>S(W3) THEN SH=S(N1): S(N1)=S(W3): S(W3)=SH: V=1
61280 NEXT N1
61290 IF V>0 THEN 61240
61300 GOTO 61220
61310 RETURN

The Code:

Here is an implementation of Shell Sort in Swift:

1
2
3
4
5
6
7
8
9
10
11
12
13
var arr = [64, 20, 50, 33, 72, 10, 23, -1, 4, 5]
public func shellSort(_ list: inout [Int]) {
var sublistCount = list.count / 2
while sublistCount > 0 {
for pos in 0..<sublistCount {
insertionSort(&list, start: pos, gap: sublistCount)
}
sublistCount = sublistCount / 2
}
}
shellSort(&arr)

Fast sorts:

Quicksort

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:

1
2
3
4
5
6
7
8
9
10
func quicksort<T: Comparable>(_ a: [T]) -> [T] {
guard a.count > 1 else { return a }
let pivot = a[a.count/2]
let less = a.filter { $0 < pivot }
let equal = a.filter { $0 == pivot }
let greater = a.filter { $0 > pivot }
return quicksort(less) + equal + quicksort(greater)
}

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

1
2
let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
quicksort(list)

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:

1
[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

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:

1
2
3
less: [ 0, 3, 2, 1, 5, -1 ]
equal: [ 8, 8 ]
greater: [ 10, 9, 14, 27, 26 ]

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:

1
[ 0, 3, 2, 1, 5, -1 ]

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:

1
2
3
less: [ 0, -1 ]
equal: [ 1 ]
greater: [ 3, 2, 5 ]

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

1
[ 0, -1 ]

As pivot we pick -1. Now the subarrays are:

1
2
3
less: [ ]
equal: [ -1 ]
greater: [ 0 ]

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:

1
[ 3, 2, 5 ]

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

1
2
3
less: [ ]
equal: [ 2 ]
greater: [ 3, 5 ]

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:

1
2
3
less: [ 3 ]
equal: [ 5 ]
greater: [ ]

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:

Example

Now if you read the colored boxes from left to right, you get the sorted array:

1
[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]

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,

1
[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

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

1
2
3
[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]
----------------- -----------------
all elements < 8 all elements > 8

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 8you could also end up with something like this:

1
[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
let pivot = a[high]
var i = low
for j in low..<high {
if a[j] <= pivot {
(a[i], a[j]) = (a[j], a[i])
i += 1
}
}
(a[i], a[high]) = (a[high], a[i])
return i
}

To test this in a playground, do:

1
2
3
var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
let p = partitionLomuto(&list, low: 0, high: list.count - 1)
list // show the results

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:

1
2
[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]
*

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 p-1 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 8s 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:

  1. a[low...i] contains all values <= pivot
  2. a[i+1...j-1] contains all values > pivot
  3. a[j...high-1] are values we haven’t looked at yet
  4. a[high] is the pivot value

In ASCII art the array is divided up like this:

1
2
[ values <= pivot | values > pivot | not looked at yet | pivot ]
low i i+1 j-1 j high-1 high

The loop looks at each element from low to high-1 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 of x and y. You can also write swap(&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:

1
2
3
4
[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j

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.

1
2
3
4
[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j

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.

1
2
3
4
[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j

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:

1
2
3
4
[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j

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

1
2
3
4
[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
low high
i
j

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

1
2
3
[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
low high
i j

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

1
2
3
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]
low high
i j

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:

1
2
3
4
5
6
7
func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = partitionLomuto(&a, low: low, high: high)
quicksortLomuto(&a, low: low, high: p - 1)
quicksortLomuto(&a, low: p + 1, high: high)
}
}

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:

1
2
var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quicksortLomuto(&list, low: 0, high: list.count - 1)

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
let pivot = a[low]
var i = low - 1
var j = high + 1
while true {
repeat { j -= 1 } while a[j] > pivot
repeat { i += 1 } while a[i] < pivot
if i < j {
a.swapAt(i, j)
} else {
return j
}
}
}

To test this in a playground, do:

1
2
3
var list = [ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]
let p = partitionHoare(&list, low: 0, high: list.count - 1)
list // show the results

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:

1
[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]

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:

1
2
3
4
5
6
7
func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = partitionHoare(&a, low: low, high: high)
quicksortHoare(&a, low: low, high: p)
quicksortHoare(&a, low: p + 1, high: high)
}
}

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,

1
[ 7, 6, 5, 4, 3, 2, 1 ]

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

1
2
3
less than pivot: [ ]
equal to pivot: [ 1 ]
greater than pivot: [ 7, 6, 5, 4, 3, 2 ]

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

1
2
3
less than pivot: [ ]
equal to pivot: [ 2 ]
greater than pivot: [ 7, 6, 5, 4, 3 ]

And again:

1
2
3
less than pivot: [ ]
equal to pivot: [ 3 ]
greater than pivot: [ 7, 6, 5, 4 ]

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:

1
2
3
less than pivot: [ 3, 2, 1 ]
equal to pivot: [ 4 ]
greater than pivot: [ 7, 6, 5 ]

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:

1
[ 7, 6, 5, 1, 4, 3, 2 ]

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 chicken-and-egg problem. However, there are some tricks to choose good, if not ideal, pivots.

One trick is “median-of-three”, 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:

1
2
3
4
5
6
7
8
9
10
11
func quicksortRandom<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let pivotIndex = random(min: low, max: high) // 1
(a[pivotIndex], a[high]) = (a[high], a[pivotIndex]) // 2
let p = partitionLomuto(&a, low: low, high: high)
quicksortRandom(&a, low: low, high: p - 1)
quicksortRandom(&a, low: p + 1, high: high)
}
}

There are two important differences with before:

  1. The random(min:max:) function returns an integer in the range min...max, inclusive. This is our pivot index.
  2. Because the Lomuto scheme expects a[high] to be the pivot entry, we swap a[pivotIndex] with a[high] to put the pivot element at the end before calling partitionLomuto().

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:

1
[ values < pivot | values equal to pivot | values > pivot ]

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func partitionDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -> (Int, Int) {
let pivot = a[pivotIndex]
var smaller = low
var equal = low
var larger = high
while equal <= larger {
if a[equal] < pivot {
swap(&a, smaller, equal)
smaller += 1
equal += 1
} else if a[equal] == pivot {
equal += 1
} else {
swap(&a, equal, larger)
larger -= 1
}
}
return (smaller, larger)
}

This works very similarly to the Lomuto scheme, except that the loop partitions the array into four (possibly empty) regions:

  • [low ... smaller-1] contains all values < pivot
  • [smaller ... equal-1] 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:

1
2
3
var list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
partitionDutchFlag(&list, low: 0, high: list.count - 1, pivotIndex: 10)
list // show the results

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

1
[ -1, 0, 3, 2, 5, 1, 8, 8, 27, 14, 9, 26, 10 ]

Notice how the two 8s 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:

1
2
3
4
5
6
7
8
func quicksortDutchFlag<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let pivotIndex = random(min: low, max: high)
let (p, q) = partitionDutchFlag(&a, low: low, high: high, pivotIndex: pivotIndex)
quicksortDutchFlag(&a, low: low, high: p - 1)
quicksortDutchFlag(&a, low: q + 1, high: high)
}
}

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 custom swap() routine for swapping the contents of two array elements. Unlike Swift’s own swap(), 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, merge-sort is an efficient algorithm with a best, worst, and average time complexity of O(n log n).

The merge-sort algorithm uses the divide and conquer approach which is to divide a big problem into smaller problems and solve them. I think of the merge-sort algorithm as split first and merge after.

Assume you need to sort an array of n numbers in the right order. The merge-sort 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].

Top-down implementation

Here’s what merge sort may look like in Swift:

1
2
3
4
5
6
7
8
9
10
11
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
let middleIndex = array.count / 2 // 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4
return merge(leftPile: leftArray, rightPile: rightArray) // 5
}

A step-by-step explanation of how the code works:

  1. 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.
  2. Find the middle index.
  3. Using the middle index from the previous step, recursively split the left side of the array.
  4. Also, recursively split the right side of the array.
  5. Finally, merge all the values together, making sure that it is always sorted.

Here’s the merging algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var orderedPile = [Int]()
orderedPile.reserveCapacity(leftPile.count + rightPile.count)
// 3
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}

This method may look scary, but it is quite straightforward:

  1. You need two indexes to keep track of your progress for the two arrays while merging.
  2. 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.
  3. This while-loop 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.
  4. If control exits from the previous while-loop, it means that either the leftPile or the rightPile has its contents completely merged into the orderedPile. 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:

1
2
3
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r

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.

1
2
3
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1 ]
-->l r

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:

1
2
3
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l -->r

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:

1
2
3
4
5
6
7
8
9
10
11
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l -->r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
-->l r

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 left-to-right 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

Bottom-up implementation

The implementation of the merge-sort algorithm you have seen so far is called the “top-down” 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 “bottom-up” approach.

Time to step up the game a little. :-) Here is a complete bottom-up implementation in Swift:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
let n = a.count
var z = [a, a] // 1
var d = 0
var width = 1
while width < n { // 2
var i = 0
while i < n { // 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { // 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
} else {
z[1 - d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1 - d // 5
}
return z[d]
}

It looks a lot more intimidating than the top-down version, but notice that the main body includes the same three whileloops from merge().

Notable points:

  1. The Merge-sort 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 array z[d] is used for reading, and z[1 - d] is used for writing. This is called double-buffering.
  2. Conceptually, the bottom-up version works the same way as the top-down 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 is 1 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.
  3. 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].
  4. This is the same logic as in the top-down version. The main difference is that we’re using double-buffering, so values are read from z[d] and written into z[1 - d]. It also uses an isOrderedBefore function to compare the elements rather than just <, so this merge-sort algorithm is generic, and you can use it to sort any kind of object you want.
  5. At this point, the piles of size width from array z[d] have been merged into larger piles of size width * 2 in array z[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 isOrderedBeforeclosure to compare the elements.

Example of how to use it:

1
2
let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]

Performance

The speed of the merge-sort 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 merge-sort 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 merge-sort algorithm is that it needs a temporary “working” array equal in size to the array being sorted. It is not an in-place sort, unlike for example quicksort.

Most implementations of the merge-sort 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

heapSort

Sorting_heapsort_anim

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 max-heap, so that the first element in the array is the largest.

Let’s say the array to sort is:

1
[ 5, 13, 2, 25, 7, 17, 20, 8, 4 ]

This is first turned into a max-heap that looks like this:

The max-heap

The heap’s internal array is then:

1
[ 25, 13, 20, 8, 7, 17, 2, 5, 4 ]

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 n-1, to get:

1
2
[ 4, 13, 20, 8, 7, 17, 2, 5, 25 ]
* *

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

1
[20, 13, 17, 8, 7, 4, 2, 5 | 25]

Important: When we fix the heap, we ignore the last item at index n-1. 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 n-2):

1
2
[5, 13, 17, 8, 7, 4, 2, 20 | 25]
* *

And fix up the heap to make it valid max-heap again:

1
[17, 13, 5, 8, 7, 4, 2 | 20, 25]

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 in-place. 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:

1
2
3
4
5
6
7
8
9
extension Heap {
public mutating func sort() -> [T] {
for i in stride(from: (elements.count - 1), through: 1, by: -1) {
swap(&elements[0], &elements[i])
shiftDown(0, heapSize: i)
}
return elements
}
}

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

1
2
var h1 = Heap(array: [5, 13, 2, 25, 7, 17, 20, 8, 4], sort: >)
let a1 = h1.sort()

Because we need a max-heap to sort from low-to-high, 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 low-to-high creates a max-heap and turns it into a min-heap.

We can write a handy helper function for that:

1
2
3
4
5
public func heapsort<T>(_ a: [T], _ sort: @escaping (T, T) -> Bool) -> [T] {
let reverseOrder = { i1, i2 in sort(i2, i1) }
var h = Heap(array: a, sort: reverseOrder)
return h.sort()
}

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure sort(A : array):
let maxdepth = ⌊log(length(A))⌋ × 2
introSort(A, maxdepth)
procedure introsort(A, maxdepth):
n ← length(A)
if n < 20:
insertionsort(A)
else if maxdepth = 0:
heapsort(A)
else:
p ← partition(A) // the pivot is selected using median of 3
introsort(A[0:p], maxdepth - 1)
introsort(A[p+1:n], maxdepth - 1)

An example

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

1
[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

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.

1
[ 10, 8, 26 ] -> [ 8, 10, 26 ]

Our array is now

1
[ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]

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.

1
[ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10, 27, 14, 26 ]

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:

1
2
less: [ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10 ]
greater: [ 27, 14, 26 ]

maxDepth: 1, branch: less

1
[ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10 ]

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.

1
2
3
4
5
6
7
8
array: [ 8, 0, 3, 9, 2, 1, 5, 8, -1, 10 ]
pivot candidates: [ 8, 1, 10] -> [ 1, 8, 10]
pivot: 8
before partition: [ 1, 0, 3, 9, 2, 8, 5, 8, -1, 10 ]
after partition: [ 1, 0, 3, -1, 2, 5, 8, 8, 9, 10 ]
less: [ 1, 0, 3, -1, 2, 5, 8 ]
greater: [ 8, 9, 10 ]

maxDepth: 0, branch: less

1
[ 1, 0, 3, -1, 2, 5, 8 ]

Just like before, introsort is recursively executed for less and greater. This time lesshas 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.

1
heapsort -> [ -1, 0, 1, 2, 3, 5, 8 ]

maxDepth: 0, branch: greater

1
[ 8, 9, 10 ]

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

1
insertionSort -> [ 8, 9 , 10]

back to maxDepth = 1, branch: greater

1
[ 27, 14, 26 ]

At this point the original array has mutated to be

1
[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 27, 14, 26 ]

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

1
[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]

Special-purpose sorts:

Counting Sort

countingSort

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:

1
2
Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 1 1 0 0 0 2 1 1 1

Here is the code to accomplish this:

1
2
3
4
5
6
let maxElement = array.max() ?? 0
var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
for element in array {
countArray[element] += 1
}

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:

1
2
Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 2 3 3 3 3 5 6 7 8

The code for step 2 is:

1
2
3
4
for index in 1 ..< countArray.count {
let sum = countArray[index] + countArray[index - 1]
countArray[index] = sum
}

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:

1
2
Index 0 1 2 3 4 5 6 7
Output 1 2 3 7 7 8 9 10

Here is the code for this final step:

1
2
3
4
5
6
var sortedArray = [Int](repeating: 0, count: array.count)
for element in array {
countArray[element] -= 1
sortedArray[countArray[element]] = element
}
return sortedArray

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

radixSort

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:

Example

This graph has two possible topological sorts:

Example

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:

Example

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 depth-first search as well as a stack. But before you can learn about the depth-first 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:

Example

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 in-degree of 0

The in-degree of a vertex is the number of edges pointing at that vertex. Vertices with no incoming edges have an in-degree 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 depth-first search

Depth-first 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 depth-first search, please take a look at the detailed explanation.

We perform a depth-first search on each vertex with in-degree 0. This tells us which vertices are connected to each of these starting vertices.

Step 3: Remember all visited vertices

As we perform the depth-first 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 depth-first searches and put the vertices in a sorted list.

Example

Consider the following graph:

Graph Example

Step 1: The vertices with 0 in-degree are: 3, 7, 5. These are our starting vertices.

Step 2: Perform depth-first search for each starting vertex, without remembering vertices that have already been visited:

1
2
3
Vertex 3: 3, 10, 8, 9
Vertex 7: 7, 11, 2, 8, 9
Vertex 5: 5, 11, 2, 9, 10

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

1
2
3
Vertex 3: 3, 10, 8, 9
Vertex 7: 7, 11, 2
Vertex 5: 5

Step 4: Combine the results of these three depth-first 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:

Result of the sort

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):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
extension Graph {
public func topologicalSort() -> [Node] {
// 1
let startNodes = calculateInDegreeOfNodes().filter({ _, indegree in
return indegree == 0
}).map({ node, indegree in
return node
})
// 2
var visited = [Node : Bool]()
for (node, _) in adjacencyLists {
visited[node] = false
}
// 3
var result = [Node]()
for startNode in startNodes {
result = depthFirstSearch(startNode, visited: &visited) + result
}
// 4
return result
}
}

Some remarks:

  1. Find the in-degree of each vertex and put all the vertices with in-degree 0 in the startNodes array. In this graph implementation, vertices are called “nodes”. Both terms are used interchangeably by people who write graph code.
  2. The visited array keeps track of whether we’ve already seen a vertex during the depth-first search. Initially, we set all elements to false.
  3. For each of the vertices in the startNodes array, perform a depth-first search. This returns an array of sorted Nodeobjects. We prepend that array to our own result array.
  4. The result array contains all the vertices in topologically sorted order.

Note: For a slightly different implementation of topological sort using depth-first search, see TopologicalSort3.swift. This uses a stack and does not require you to find all vertices with in-degree 0 first.

Kahn’s algorithm

Even though depth-first search is the typical way to perform a topological sort, there is another algorithm that also does the job.

  1. Find out what the in-degree is of every vertex.
  2. Put all the vertices that have no predecessors in a new array called leaders. These vertices have in-degree 0 and therefore do not depend on any other vertices.
  3. Go through this list of leaders and remove them one-by-one from the graph. We don’t actually modify the graph, we just decrement the in-degree of the vertices they point to. That has the same effect.
  4. Look at the (former) immediate neighbor vertices of each leader. If any of them now have an in-degree of 0, then they no longer have any predecessors themselves. We’ll add those vertices to the leaders array too.
  5. 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

bubbleSort

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

1
2
3
4
5
6
7
8
9
10
for i in 0..<array.count {
for j in 1..<array.count {
if array[j] < array[j-1] {
let tmp = array[j-1]
array[j-1] = array[j]
array[j] = tmp
}
}
}
return array

Optimization

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

1
2
3
4
5
6
7
8
9
10
for i in 0..<array.count {
for j in 1..<array.count - i {
if array[j] < array[j-1] {
let tmp = array[j-1]
array[j-1] = array[j]
array[j] = tmp
}
}
}
return array

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

  1. find the maximum of the numbers
  2. find the maximum of the first n/2 elements
  3. find the maximum of the remaining n/2 elements
  4. find the largest of those two maxima
  5. sorting the remaining ones

The code

Here is an implementation of slow sort in Swift:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public func slowsort(_ i: Int, _ j: Int) {
if i>=j {
return
}
let m = (i+j)/2
slowsort(i,m)
slowsort(m+1,j)
if numberList[j] < numberList[m] {
let temp = numberList[j]
numberList[j] = numberList[m]
numberList[m] = temp
}
slowsort(i,j-1)
}

Performance

WORST!

See also

Slow Sort explanation in the Internet

Reference

swift-algorithm-club

Top 10 classic sorting algorithms

算法艺术与信息学竞赛(刘汝佳、黄亮)

Title: Several sorting algorithms

Author: Tuski

Published: 06/18/2019 - 16:02:42

Updated: 06/19/2019 - 20:37:54

Link: http://www.perphet.com/2019/06/Several-sorting-algorithms/

Protocol: Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Reprinted please keep the original link and author

Thx F Sup