Writing merge sort in-place in Swift

A quick look on how to write an in-place merge sort.

Once in a while I like to review some sorting algorithms, the same with data structures. This week I was reviewing the merge sort.

I followed some tutorials to remind me. You can follow one of them here: https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort

One thing that bothered me is the space necessary for this algorithm to work. Basically we create copies of the list, till we have a list with only one element.

I proposed myself a challenge of writing this in-place. I have no doubt there are some algorithms doing something similar out there, but I just did want to have fun.

As many of you may know, merge sort is a recursive algorithm. We will first write the function that will call itself. We'll name it merge sort. It will receive the list as a parameter. A left and a right int, representing the first and the last element of that list. We will use them instead of creating new lists all the time. This is why our list is inout — because we'll change it!

We will do nothing when the list has just one element. Meaning right pointer is equal to left. In case we have more elements, we'll divide that list in 2 lists: