Merge Sort Algorithms in Swift

1. Introduction

Merge Sort is a divide-and-conquer algorithm that divides the unsorted list into n sublists, each containing one element, and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining. It's particularly useful for sorting large datasets or linked lists.

2. Implementation Steps

1. Recursively split the list into halves until each sublist contains a single element.

2. Merge the sublists by comparing the elements to produce new sorted sublists.

3. Repeat the merging process until there's only one sorted list remaining.

3. Implementation in Swift

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    if array.count <= 1 { return array }
    let middle = array.count / 2
    let left = mergeSort(Array(array[..<middle]))
    let right = mergeSort(Array(array[middle...]))
    return merge(left, right)
}
func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    var result: [T] = []
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else {
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    while leftIndex < left.count {
        result.append(left[leftIndex])
        leftIndex += 1
    }
    while rightIndex < right.count {
        result.append(right[rightIndex])
        rightIndex += 1
    }
    return result
}
// Example Usage
let numbers = [38, 27, 43, 3, 9, 82, 10]
let sortedNumbers = mergeSort(numbers)

Output:

The sorted array will be: [3, 9, 10, 27, 38, 43, 82]

Explanation:

1. Merge Sort works on the principle of dividing the array into two halves, sorting them separately, and then merging them together.

2. The central part of the Merge Sort algorithm is the merge function that combines two sorted arrays into a single sorted array.

3. The process begins by splitting the original array down the middle into left and right sub-arrays.

4. Each sub-array is then recursively split in half until the base case is reached where each sub-array contains a single element.

5. The merge function takes over from here, merging each pair of sub-arrays in a sorted manner until the original array is reformed, but now in sorted order.

The time complexity of Merge Sort is O(n log n) in all three cases (worst, average, and best) as the array is divided into two halves. The primary advantage of Merge Sort is its consistent performance across different scenarios.