Sorting is a core skill in programming, and Swift offers many ways to sort data efficiently. One of the most interesting algorithms is Tim Sort, a hybrid sorting method that combines merge sort and insertion sort to optimize performance on real-world data. It is especially effective because many datasets are partially ordered, and Tim Sort takes advantage of this by finding small sorted sequences and merging them smartly.
with hands-on learning.
get the skills and confidence to land your next move.
Tim Sort is widely used in modern programming languages; in fact, Python and Java’s default sorting functions rely on it. It is fast, stable, and handles both small and large datasets well. For beginners, learning Tim Sort helps understand the value of hybrid algorithms, combining the simplicity of insertion sort for small sequences with the efficiency of merge sort for larger datasets.
Program 1: Basic Tim Sort with Loops and Merge
This program demonstrates a simple Tim Sort implementation using loops and the basic merge technique. It starts by splitting the array into small sorted runs and then merges them together.
import Foundation
func insertionSort<T: Comparable>(_ array: inout [T], left: Int, right: Int) {
for i in (left + 1)...right {
let temp = array[i]
var j = i - 1
while j >= left && array[j] > temp {
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = temp
}
}
func merge<T: Comparable>(_ array: inout [T], left: Int, mid: Int, right: Int) {
let leftArray = Array(array[left...mid])
let rightArray = Array(array[(mid + 1)...right])
var i = 0, j = 0, k = left
while i < leftArray.count && j < rightArray.count {
if leftArray[i] <= rightArray[j] {
array[k] = leftArray[i]
i += 1
} else {
array[k] = rightArray[j]
j += 1
}
k += 1
}
while i < leftArray.count {
array[k] = leftArray[i]
i += 1
k += 1
}
while j < rightArray.count {
array[k] = rightArray[j]
j += 1
k += 1
}
}
func timSortBasic<T: Comparable>(_ array: inout [T]) {
let n = array.count
let run = 32
var i = 0
while i < n {
insertionSort(&array, left: i, right: min(i + run - 1, n - 1))
i += run
}
var size = run
while size < n {
var left = 0
while left < n {
let mid = min(left + size - 1, n - 1)
let right = min(left + 2 * size - 1, n - 1)
if mid < right {
merge(&array, left: left, mid: mid, right: right)
}
left += 2 * size
}
size *= 2
}
}
var data1 = [23, 42, 4, 16, 8, 15, 9, 55]
timSortBasic(&data1)
print("Sorted array (basic Tim Sort):", data1)This approach demonstrates how Tim Sort breaks an array into small sorted runs using insertion sort and then merges them efficiently. Beginners can understand it as a smart combination of simple and efficient sorting techniques.
Program 2: Tim Sort with Custom Run Size
Sometimes performance can be improved by adjusting the run size. This version allows specifying a different run size for the insertion sort stage.
import Foundation
func insertionSort<T: Comparable>(_ array: inout [T], left: Int, right: Int) {
for i in (left + 1)...right {
let temp = array[i]
var j = i - 1
while j >= left && array[j] > temp {
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = temp
}
}
func merge<T: Comparable>(_ array: inout [T], left: Int, mid: Int, right: Int) {
let leftArray = Array(array[left...mid])
let rightArray = Array(array[(mid + 1)...right])
var i = 0, j = 0, k = left
while i < leftArray.count && j < rightArray.count {
if leftArray[i] <= rightArray[j] {
array[k] = leftArray[i]
i += 1
} else {
array[k] = rightArray[j]
j += 1
}
k += 1
}
while i < leftArray.count {
array[k] = leftArray[i]
i += 1
k += 1
}
while j < rightArray.count {
array[k] = rightArray[j]
j += 1
k += 1
}
}
func timSortCustomRun<T: Comparable>(_ array: inout [T], runSize: Int) {
let n = array.count
var i = 0
while i < n {
insertionSort(&array, left: i, right: min(i + runSize - 1, n - 1))
i += runSize
}
var size = runSize
while size < n {
var left = 0
while left < n {
let mid = min(left + size - 1, n - 1)
let right = min(left + 2 * size - 1, n - 1)
if mid < right {
merge(&array, left: left, mid: mid, right: right)
}
left += 2 * size
}
size *= 2
}
}
var data2 = [12, 7, 14, 3, 19, 8, 6]
timSortCustomRun(&data2, runSize: 16)
print("Sorted array (custom run size):", data2)Adjusting the run size lets beginners experiment with performance optimization. Smaller runs rely more on insertion sort, which is efficient for small arrays, while larger runs emphasize merging efficiency.
Program 3: Tim Sort Returning a New Array
If you prefer not to modify the original array, this version of Tim Sort returns a new sorted array instead.
import Foundation
func insertionSort<T: Comparable>(_ array: inout [T], left: Int, right: Int) {
for i in (left + 1)...right {
let temp = array[i]
var j = i - 1
while j >= left && array[j] > temp {
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = temp
}
}
func merge<T: Comparable>(_ array: inout [T], left: Int, mid: Int, right: Int) {
let leftArray = Array(array[left...mid])
let rightArray = Array(array[(mid + 1)...right])
var i = 0, j = 0, k = left
while i < leftArray.count && j < rightArray.count {
if leftArray[i] <= rightArray[j] {
array[k] = leftArray[i]
i += 1
} else {
array[k] = rightArray[j]
j += 1
}
k += 1
}
while i < leftArray.count {
array[k] = leftArray[i]
i += 1
k += 1
}
while j < rightArray.count {
array[k] = rightArray[j]
j += 1
k += 1
}
}
func timSortBasic<T: Comparable>(_ array: inout [T]) {
let n = array.count
let run = 32
var i = 0
while i < n {
insertionSort(&array, left: i, right: min(i + run - 1, n - 1))
i += run
}
var size = run
while size < n {
var left = 0
while left < n {
let mid = min(left + size - 1, n - 1)
let right = min(left + 2 * size - 1, n - 1)
if mid < right {
merge(&array, left: left, mid: mid, right: right)
}
left += 2 * size
}
size *= 2
}
}
func timSortReturn<T: Comparable>(_ array: [T]) -> [T] {
var sortedArray = array
timSortBasic(&sortedArray)
return sortedArray
}
let data3 = [33, 10, 55, 71, 22]
let sortedData3 = timSortReturn(data3)
print("Sorted array (returned new array):", sortedData3)Returning a new array can be safer when working with immutable data or when the original array must remain unchanged.
Program 4: Tim Sort with Floating-Point Numbers
Tim Sort works for any comparable type, including floating-point numbers. This example demonstrates sorting an array of doubles.
import Foundation
func insertionSort<T: Comparable>(_ array: inout [T], left: Int, right: Int) {
for i in (left + 1)...right {
let temp = array[i]
var j = i - 1
while j >= left && array[j] > temp {
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = temp
}
}
func merge<T: Comparable>(_ array: inout [T], left: Int, mid: Int, right: Int) {
let leftArray = Array(array[left...mid])
let rightArray = Array(array[(mid + 1)...right])
var i = 0, j = 0, k = left
while i < leftArray.count && j < rightArray.count {
if leftArray[i] <= rightArray[j] {
array[k] = leftArray[i]
i += 1
} else {
array[k] = rightArray[j]
j += 1
}
k += 1
}
while i < leftArray.count {
array[k] = leftArray[i]
i += 1
k += 1
}
while j < rightArray.count {
array[k] = rightArray[j]
j += 1
k += 1
}
}
func timSortBasic<T: Comparable>(_ array: inout [T]) {
let n = array.count
let run = 32
var i = 0
while i < n {
insertionSort(&array, left: i, right: min(i + run - 1, n - 1))
i += run
}
var size = run
while size < n {
var left = 0
while left < n {
let mid = min(left + size - 1, n - 1)
let right = min(left + 2 * size - 1, n - 1)
if mid < right {
merge(&array, left: left, mid: mid, right: right)
}
left += 2 * size
}
size *= 2
}
}
var data4: [Double] = [0.12, 0.55, 0.34, 0.78, 0.22]
timSortBasic(&data4)
print("Sorted array (doubles):", data4)This shows that Tim Sort is versatile, making it suitable for real-world datasets where numbers may not always be integers.
Program 5: Generic Tim Sort Using Comparable Types
By using Swift generics, Tim Sort can handle any type that conforms to Comparable. This makes the function reusable for integers, doubles, or even custom objects.
import Foundation
func insertionSort<T: Comparable>(_ array: inout [T], left: Int, right: Int) {
for i in (left + 1)...right {
let temp = array[i]
var j = i - 1
while j >= left && array[j] > temp {
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = temp
}
}
func merge<T: Comparable>(_ array: inout [T], left: Int, mid: Int, right: Int) {
let leftArray = Array(array[left...mid])
let rightArray = Array(array[(mid + 1)...right])
var i = 0, j = 0, k = left
while i < leftArray.count && j < rightArray.count {
if leftArray[i] <= rightArray[j] {
array[k] = leftArray[i]
i += 1
} else {
array[k] = rightArray[j]
j += 1
}
k += 1
}
while i < leftArray.count {
array[k] = leftArray[i]
i += 1
k += 1
}
while j < rightArray.count {
array[k] = rightArray[j]
j += 1
k += 1
}
}
func timSortBasic<T: Comparable>(_ array: inout [T]) {
let n = array.count
let run = 32
var i = 0
while i < n {
insertionSort(&array, left: i, right: min(i + run - 1, n - 1))
i += run
}
var size = run
while size < n {
var left = 0
while left < n {
let mid = min(left + size - 1, n - 1)
let right = min(left + 2 * size - 1, n - 1)
if mid < right {
merge(&array, left: left, mid: mid, right: right)
}
left += 2 * size
}
size *= 2
}
}
func timSortGeneric<T: Comparable>(_ array: [T]) -> [T] {
var sortedArray = array
timSortBasic(&sortedArray)
return sortedArray
}
let data5 = [5, 3, 8, 1, 2]
let sortedData5 = timSortGeneric(data5)
print("Sorted array (generic):", sortedData5)Generics demonstrate the power of reusable Swift functions, allowing the same algorithm to sort different types without rewriting the code.
Frequently Asked Questions (FAQ)
This section answers common questions beginners ask about Tim Sort in Swift.
Q1: Why is Tim Sort better than merge sort alone?
Tim Sort optimizes for partially sorted arrays by using insertion sort on small runs, reducing the number of comparisons needed for real-world data.
Q2: Can Tim Sort handle floating-point numbers?
Yes, Tim Sort works with any data type that conforms to the Comparable protocol, including doubles.
Q3: What is the best run size to use?
A typical default is 32, but experimenting with different run sizes can sometimes improve performance.
Q4: Is Tim Sort stable?
Yes, Tim Sort is a stable sorting algorithm, meaning equal elements retain their original order.
Q5: Can Tim Sort sort custom objects?
Yes, as long as the objects conform to Comparable, Tim Sort can sort them just like numbers.
Conclusion
Tim Sort is a powerful hybrid sorting algorithm that combines the simplicity of insertion sort for small sequences with the efficiency of merge sort for larger arrays. In Swift, it can be implemented using loops, custom run sizes, generics, or functions returning new arrays. By practicing Tim Sort on integers, floating-point numbers, and custom types, beginners can gain a solid understanding of hybrid sorting techniques and develop flexible, efficient sorting solutions.
