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.
DSA
Related Swift Examples:
Swift Hello World Program
Swift Program to Add Two Numbers
Swift Program to Subtract Two Numbers
Swift Program to Multiply Two Numbers
Swift Program to Divide Two Numbers
Swift Program to Find Remainder
Swift Program to Check Even or Odd
Swift Program to Find Factorial of a Number
Swift Program to Generate Fibonacci Series
Swift Program to Swap Two Numbers Without Using Temporary Variable
Swift Program to Find Largest Among Three Numbers
Swift Program to Calculate the Area of a Circle
Swift Program to Reverse a Number
Swift Program to Make a Simple Calculator
Swift Program to Check Palindrome
Swift Program to Count Number of Digits in an Integer
Swift Program to Sum of Natural Numbers
Swift Program to Display Times Table
Swift Program to Check Prime Number
Swift Program to Find LCM
Swift Program to Find GCD
Swift Program to Find the Power of a Number
Swift Program to Split a String into Words
Swift Program to Check Leap Year
Swift Program to Join Two Strings
Swift Program to Check Armstrong Number
Swift Program to Find Sum of Array Elements
Swift Program to Find the Largest Element of an Array
Swift Program to Perform Matrix Addition
Swift Program to Transpose a Matrix
Swift Program to Multiply Two Matrices
Swift Program to Find Length of a String
Swift Program to Copy One String to Another String
Swift Program to Concatenate Two Strings
Swift Program to Search for a Character in a String
Swift Program to Count Frequency of a Character in String
Swift Program to Create a Simple Class and Object
Swift Program to Implement Inheritance
Swift Program to Handle Simple Exceptions
Swift Variables and Constants Example
Swift Data Types (Int, Double, String) Example
Swift Optionals and Optional Binding Example
Swift Tuples Example
Swift Array Example
Swift Dictionary Example
Swift Set Example
Swift Closures Example
Swift Enums Example
Swift Structures Example
Swift Properties (Stored, Computed) Example
Swift Methods (Instance, Type) Example
Swift Subscripts Example
Swift Inheritance and Overriding Example
Swift Protocols Example
Swift Extensions Example
Swift Generics and Generic Functions Example
Swift Error Handling with Do-Catch Example
Swift Guard Statement Example
Swift Defer Statement Example
Swift Type Casting (as, is, as?) Example
Swift Access Control Example
Swift Attributes (@available, @discardableResult) Example
Swift Pattern Matching Example
Swift Switch Statement and Cases Example
Swift For-In Loop Example
Swift While and Repeat-While Loops Example
Swift Conditional Statements (If, If-Else, Ternary) Example
Swift Operators Example
Swift Memory Management Example
Swift Strong, Weak, and Unowned References Example
Swift Initialization and Deinitialization Example
Swift Protocol-Oriented Programming Example
Swift Nested Types Example
Swift Type Aliases Example
Swift Dynamic Member Lookup Example
Swift Lazy Stored Properties Example
Swift KeyPaths Example
Swift String Manipulation and Methods Example
Swift Regular Expressions Example
Swift
Comments
Post a Comment