Merge sort is a powerful and important sorting algorithm that many beginners eventually grow to appreciate because of its clean and predictable structure. Unlike simpler sorting methods such as insertion sort or bubble sort, merge sort works by dividing the list into smaller halves, sorting those halves, and then combining them in a careful and ordered way. This method follows the idea of “divide and conquer,” which is a common strategy used in many advanced algorithms. Once you understand merge sort, it becomes easier to learn other strong algorithms later on.
with hands-on learning.
get the skills and confidence to land your next move.
What makes merge sort special is its speed and reliability, especially when dealing with large amounts of data. It is used in real systems where efficiency matters, such as search engines, databases, and software tools that manage large lists. Even though the idea may feel slightly different from the usual step-by-step sorting, merge sort is friendly once you break it down. The best part is that Swift can express the algorithm in a very clear way, making it perfect for beginners who want to grow their confidence.
Program 1: Basic Merge Sort Using Recursion
This first program shows the classic version of merge sort using recursion. It splits the array into halves, sorts each half, and then merges them again in sorted order. This helps beginners see the natural flow of divide, sort, and join.
import Foundation
func mergeSort(_ arr: [Int]) -> [Int] {
if arr.count <= 1 {
return arr
}
let mid = arr.count / 2
let left = mergeSort(Array(arr[0..<mid]))
let right = mergeSort(Array(arr[mid..<arr.count]))
return merge(left, right)
}
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
var merged: [Int] = []
var i = 0
var j = 0
while i < left.count && j < right.count {
if left[i] <= right[j] {
merged.append(left[i])
i += 1
} else {
merged.append(right[j])
j += 1
}
}
merged.append(contentsOf: left[i...])
merged.append(contentsOf: right[j...])
return merged
}
let data = [38, 27, 43, 3, 9, 82, 10]
let sorted = mergeSort(data)
print("Sorted Array:", sorted)This version works by repeatedly cutting the array in half until each piece has one element. Once the pieces are tiny, they are merged step by step into sorted order. Beginners understand this approach well because the splitting and merging feel natural once seen in action.
Program 2: Merge Sort With a Clearer Merge Function
This program uses the same idea but rewrites the merge function in a more beginner-friendly way. It improves readability so you can focus on how the merging actually happens. The main merge sort function stays the same.
import Foundation
func mergeSort2(_ arr: [Int]) -> [Int] {
if arr.count < 2 {
return arr
}
let mid = arr.count / 2
let left = mergeSort2(Array(arr[0..<mid]))
let right = mergeSort2(Array(arr[mid..<arr.count]))
return mergeSimple(left, right)
}
func mergeSimple(_ left: [Int], _ right: [Int]) -> [Int] {
var L = left
var R = right
var result: [Int] = []
while !L.isEmpty && !R.isEmpty {
if L.first! <= R.first! {
result.append(L.removeFirst())
} else {
result.append(R.removeFirst())
}
}
result.append(contentsOf: L)
result.append(contentsOf: R)
return result
}
let list = [20, 7, 1, 54, 23]
let output = mergeSort2(list)
print("Sorted Array:", output)This method helps beginners understand merging by using clear variable names and removing elements from the front. Even though removing from the front is not the fastest method, it is very easy to understand, which makes it perfect for learners.
Program 3: Merge Sort in Descending Order
This program sorts values from highest to lowest instead of lowest to highest. The change happens inside the comparison, showing how flexible merge sort can be with only small adjustments.
import Foundation
func mergeSortDescending(_ arr: [Int]) -> [Int] {
if arr.count <= 1 {
return arr
}
let mid = arr.count / 2
let left = mergeSortDescending(Array(arr[0..<mid]))
let right = mergeSortDescending(Array(arr[mid..<arr.count]))
return mergeDescending(left, right)
}
func mergeDescending(_ left: [Int], _ right: [Int]) -> [Int] {
var L = left
var R = right
var result: [Int] = []
while !L.isEmpty && !R.isEmpty {
if L.first! >= R.first! {
result.append(L.removeFirst())
} else {
result.append(R.removeFirst())
}
}
result.append(contentsOf: L)
result.append(contentsOf: R)
return result
}
let values = [5, 12, 3, 19, 7]
let sortedDesc = mergeSortDescending(values)
print("Sorted Descending:", sortedDesc)This version is useful when you want high scores or large numbers first. It also shows beginners how algorithms can shift direction with very small changes in the logic.
Program 4: Merge Sort Using a Single Merge Function With Indices
This version avoids removing elements or slicing arrays. Instead, it uses index pointers, which is closer to how merge sort works efficiently in real systems. It uses recursion but in a way that saves memory.
import Foundation
func mergeSortIndex(_ arr: inout [Int], _ temp: inout [Int], _ left: Int, _ right: Int) {
if left >= right {
return
}
let mid = (left + right) / 2
mergeSortIndex(&arr, &temp, left, mid)
mergeSortIndex(&arr, &temp, mid + 1, right)
mergeIndex(&arr, &temp, left, mid, right)
}
func mergeIndex(_ arr: inout [Int], _ temp: inout [Int], _ left: Int, _ mid: Int, _ right: Int) {
var i = left
var j = mid + 1
var k = left
while i <= mid && j <= right {
if arr[i] <= arr[j] {
temp[k] = arr[i]
i += 1
} else {
temp[k] = arr[j]
j += 1
}
k += 1
}
while i <= mid {
temp[k] = arr[i]
i += 1
k += 1
}
while j <= right {
temp[k] = arr[j]
j += 1
k += 1
}
for n in left...right {
arr[n] = temp[n]
}
}
var numbers = [31, 41, 59, 26, 53, 58]
var temp = Array(repeating: 0, count: numbers.count)
mergeSortIndex(&numbers, &temp, 0, numbers.count - 1)
print("Sorted Array:", numbers)This method is more efficient because it minimizes memory usage. Beginners who want to move to a more advanced style will appreciate how this form looks more like a professional algorithm.
Program 5: Merge Sort Using an Iterative Approach
This final program shows merge sort without recursion. Instead, it merges small pieces first, then bigger pieces, until the whole array becomes sorted. This gives beginners another way to understand the algorithm.
import Foundation
func mergeIndex(_ arr: inout [Int], _ temp: inout [Int], _ left: Int, _ mid: Int, _ right: Int) {
var i = left
var j = mid + 1
var k = left
while i <= mid && j <= right {
if arr[i] <= arr[j] {
temp[k] = arr[i]
i += 1
} else {
temp[k] = arr[j]
j += 1
}
k += 1
}
while i <= mid {
temp[k] = arr[i]
i += 1
k += 1
}
while j <= right {
temp[k] = arr[j]
j += 1
k += 1
}
for n in left...right {
arr[n] = temp[n]
}
}
func iterativeMergeSort(_ arr: [Int]) -> [Int] {
var nums = arr
var temp = arr
var size = 1
while size < nums.count {
var left = 0
while left < nums.count - size {
let mid = left + size - 1
let right = min(left + 2 * size - 1, nums.count - 1)
mergeIndex(&nums, &temp, left, mid, right)
left += 2 * size
}
size *= 2
}
return nums
}
let dataSet = [32, 7, 4, 90, 22, 16]
let finalSorted = iterativeMergeSort(dataSet)
print("Sorted Array:", finalSorted)This version helps beginners see how merge sort can work without recursion. Instead of splitting the array first, it builds the sorted result from smaller sorted parts. It is a nice way to understand the same idea through a different lens.
Frequently Asked Questions (FAQ)
This section explains common questions students often ask when learning merge sort.
Q1: Why is merge sort considered efficient?
It handles large data well because it works in a predictable time and follows the divide-and-conquer method.
Q2: Does merge sort always use extra memory?
Yes, most versions need extra space to store merged results, making it stable but memory-aware.
Q3: Is merge sort faster than bubble sort or insertion sort?
Yes, it usually performs much better, especially with large datasets.
Q4: Can merge sort work with negative numbers?
It works with any numbers because it only compares values.
Q5: Which version should beginners start with?
The basic recursive version is usually the easiest and clearest for new learners.
Conclusion
Merge sort may look different from the simpler sorting algorithms, but once you understand its rhythm of splitting and merging, it becomes clear and enjoyable. It teaches strong ideas like divide-and-conquer, recursion, and careful merging. The Swift programs above show several ways to express the same algorithm, helping you grow from beginner level into someone comfortable with deeper concepts. Keep practicing, try new arrays, and experiment with your own variations. With time, merge sort will feel natural, and you will be ready to explore even more advanced sorting techniques.
