Swift Coding Test Course, Merge Sort

Hello. Today, we will learn about the Merge Sort algorithm implemented in Swift. This tutorial will start from the basics of Merge Sort and explain its application in actual coding tests in detail.

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:

Given the original array, it is split into two sub-arrays at the midpoint.
Merge Sort is recursively performed on each sub-array.
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.. [Int] {
                var mergedArray: [Int] = []
                var leftIndex = 0
                var rightIndex = 0
                
                // 4. Merge by comparing the two arrays
                while leftIndex < left.count && rightIndex < right.count {
                    if left[leftIndex] < right[rightIndex] {
                        mergedArray.append(left[leftIndex])
                        leftIndex += 1
                    } else {
                        mergedArray.append(right[rightIndex])
                        rightIndex += 1
                    }
                }
                
                // 5. Add remaining elements
                while leftIndex < left.count {
                    mergedArray.append(left[leftIndex])
                    leftIndex += 1
                }
                
                while rightIndex < 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]

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:

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.
let midIndex = array.count / 2: Calculates the midpoint index of the array.
let leftArray = mergeSort(Array(array[0..: Recursively sorts the left sub-array.


let rightArray = mergeSort(Array(array[midIndex..: Recursively sorts the right sub-array.

return merge(leftArray, rightArray): Merges the sorted left and right arrays and returns the result.


In the merge function, indices are tracked as the two arrays are compared and merged. If one array is exhausted, the remaining elements are added to produce the final result.



Advantages and Disadvantages of Merge Sort
Merge Sort has the following advantages and disadvantages:
Advantages:

Stable sorting: The relative order of elements with equal values is preserved.
Time complexity of O(n log n): It provides a relatively fast sorting performance proportional to the amount of data.
Can be applied to linked lists as well as arrays of fixed size: It can be used in structures that utilize pointers.

Disadvantages:

Requires additional memory: Because a new array is created during the merging process, the space complexity is O(n).
In simpler cases (e.g., nearly sorted cases), simpler algorithms like insertion sort may perform better.



Additional Problems for Skill Improvement
Now that you understand Merge Sort, practice further with these additional problems:

Write a function that takes an array of integers and returns a sorted array with duplicates removed.
Implement an algorithm that finds the index of an element with a specific value in a sorted array using binary search.
Write a function in Swift that merges multiple input arrays into one sorted array.



This concludes our discussion on implementing Merge Sort in Swift. It is important to solidify your understanding of basic data structures and algorithm theories when solving algorithm problems. We will meet again in the next tutorial with more in-depth content. Thank you!




	관련