# Merge Sort In Swift

There are a lot of sorting algorithms. In this post we will take a look at implementing merge sort in Swift.

Hint: This post is using Swift 3

Swift has a build in array-sort algorithm which is very fast. Nevertheless it’s interesting to implement a sorting algorithm on your own – you can learn a lot by doing so.

### The idea of merge sort

The idea of merge sort is very simple: First, the list will be divided until every item is on its own. Then, new lists will be created, beginning with lists of two items. In this step it’s very straightforward to sort these small lists. Then, we combine always two list to another sorted list of four items. This steps get’s repeated until all items are sorted in one list.

### Example

Let’s take a look at an example:

We want to sort the list [98,1,45,13,6]. First, the list will be divided, the divided lists will again divided and so on. The process will be stopped, when every list has exactly one item. In the picture that is accomplished in line four. Then, always two lists will be merged. The process will be repeated until only one list is left – and this list is now sorted.

### Implementing merge sort

Now let’s implement the algorithm in Swift. There are different approaches for solving that problem, we will take a recursive one:

```import Foundation

func merge(left:[Int],right:[Int]) -> [Int] {
var mergedList = [Int]()
var left = left
var right = right

while left.count > 0 && right.count > 0 {
if left.first! < right.first! {
mergedList.append(left.removeFirst())
} else {
mergedList.append(right.removeFirst())
}
}

return mergedList + left + right
}

func mergeSort(list:[Int]) -> [Int] {
guard list.count > 1 else {
return list
}

let leftList = Array(list[0..<list.count/2])
let rightList = Array(list[list.count/2..<list.count])

return merge(left: mergeSort(list:leftList), right: mergeSort(list:rightList))
}```

The function mergeSort divides the list into two list and returns the merged and sorted list by using the function merge. Within the function call, the function calls itself recursively for both lists. When mergeSort gets a list, that has just one element, it returns the whole list.

The function merge always compares the first items of the two lists and appends the smaller item to the new sorted list.

### Testing the algorithm

Now we can test the algorithm:

```var list = [Int]()

for _ in 0..<100 {
list.append(Int(arc4random_uniform(UInt32(1000))))
}

print(list)

print()

print(mergeSort(list: list))```

Everything works as expected.

### References

Title image: @ Garsya / shutterstock.com