Writing merge sort in-place in Swift
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:
List 1: start of the current list till the middle
List 2: the element after the middle till the end of the list
To calculate the middle I used a simple math equation: left+(right-left/2)
We will repeat this process, as said before, till we have only one element. Whenever it happens, we'll call the function merge, that is supposed to merge two ordered lists.
For the merge function, it will basically receive a the initial index of the first list, the end of the first list and the end of the second list.
The merge function is where if differs most of the regular merge sort implementations. Here we need to "merge" those two lists, that are actually just one.
What I did here is, I checked each element 'x' of first list and compared to the first element of the second one, let's call it 'y'. In case x ≥ y, we would add y in the index of x, so it would be moved one position forward, and the second list would lost one element. I needed to create an updatedMiddle, to keep track of the size of the first list, as it would "grow" over time.
At the end of the execution of this function, all elements from start to end are going to me sorted.
I like that I don't have those lists being created all the time anymore, but still bothers me that the array is moving elements around every time I remove or insert an element.
If you liked this quick post, leave a like and follow me on LinkedIn! See you!