Swift Coding Test Course, Merge Sort

What is Merge Sort?

Merge Sort is a sorting algorithm based on the divide and conquer strategy. It divides the array into two halves, sorts each sub-array, and then merges the two sorted sub-arrays into one sorted array. Merge Sort has an average and worst-case time complexity of O(n log n) and is a stable sort.

Principle of Merge Sort

The process of Merge Sort is as follows:

1. Given the original array, it is split into two sub-arrays at the midpoint.
2. Merge Sort is recursively performed on each sub-array.
3. The two sorted sub-arrays are merged to create one sorted array.

The important point here is that the sub-arrays are sorted at each step. The entire array is sorted by merging these sorted arrays back together.

Problem: Sort Integers

Write a function in Swift that sorts a given list of integers in ascending order. An example input is as follows:

            let nums = [38, 27, 43, 3, 9, 82, 10]
        

To solve this problem, you need to apply the principles of Merge Sort explained above.

Implementing Merge Sort

Now, let’s implement Merge Sort in Swift. Below is the complete code:

            func mergeSort(_ array: [Int]) -> [Int] {
                // 1. If the size of the array is less than 1, return the original array
                if array.count < 2 {
                    return array
                }
                
                // 2. Split the array at the midpoint
                let midIndex = array.count / 2
                let leftArray = mergeSort(Array(array[0..<midindex])) let="" rightarray="mergeSort(Array(array[midIndex..<array.count]))" return="" merge(leftarray,="" rightarray)="" }="" func="" merge(_="" left:="" [int],="" _="" right:="" [int])="" -=""> [Int] {
                var mergedArray: [Int] = []
                var leftIndex = 0
                var rightIndex = 0
                
                // 4. Merge by comparing the two arrays
                while leftIndex &lt; left.count &amp;&amp; rightIndex &lt; right.count {
                    if left[leftIndex] &lt; right[rightIndex] {
                        mergedArray.append(left[leftIndex])
                        leftIndex += 1
                    } else {
                        mergedArray.append(right[rightIndex])
                        rightIndex += 1
                    }
                }
                
                // 5. Add remaining elements
                while leftIndex &lt; left.count {
                    mergedArray.append(left[leftIndex])
                    leftIndex += 1
                }
                
                while rightIndex &lt; right.count {
                    mergedArray.append(right[rightIndex])
                    rightIndex += 1
                }
                
                return mergedArray
            }

            // Main
            let nums = [38, 27, 43, 3, 9, 82, 10]
            let sortedNums = mergeSort(nums)
            print(sortedNums) // Result: [3, 9, 10, 27, 38, 43, 82]
        </midindex]))>

The above code sorts the input list of numbers using Merge Sort and prints the result. Comments are added at each step to aid understanding.

Code Explanation

Let's take a look at the code line by line:

1. if array.count < 2 { return array }: If the size of the array is less than 1, it is already sorted, so it is returned as is.
2. let midIndex = array.count / 2: Calculates the midpoint index of the array.
3. let leftArray = mergeSort(Array(array[0..<midindex]))< code="">: Recursively sorts the left sub-array.</midindex]))<>
<li><code>let rightArray = mergeSort(Array(array[midIndex..<array.count]))< code="">: Recursively sorts the right sub-array.</array.count]))<></code></li><code> <li><code>return merge(leftArray, rightArray)</code>: Merges the sorted left and right arrays and returns the result.</li> </code>