Mojo Sorting Algorithms
Sorting arranges a collection of values into a defined order. It is one of the most fundamental operations in computing — used in search, ranking, deduplication, and data presentation. Mojo lets you implement sorting algorithms with direct memory control and SIMD acceleration for maximum performance.
Why Learn Sorting Algorithms
You already use sorting every day: ├── Search engines rank results by relevance ├── Spreadsheets sort columns alphabetically or numerically ├── Databases use sorted indexes for fast lookups └── Machine learning sorts predictions by confidence score Understanding algorithms: ├── Teaches you how to analyze performance (Big-O) ├── Helps you choose the right tool for each situation └── Shows how Mojo's speed advantage compounds in loops
Bubble Sort
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element "bubbles" to the end on each pass.
fn bubble_sort(inout arr: List[Int]):
var n = len(arr)
for i in range(n):
var swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
swapped = True
if not swapped:
break # already sorted — stop early
fn main():
var nums = List[Int](64, 34, 25, 12, 22, 11, 90)
bubble_sort(nums)
for i in range(len(nums)):
print(nums[i], end=" ") # 11 12 22 25 34 64 90
Bubble sort pass 1 on [64, 34, 25, 12]: Compare 64,34 → swap → [34, 64, 25, 12] Compare 64,25 → swap → [34, 25, 64, 12] Compare 64,12 → swap → [34, 25, 12, 64] ← 64 bubbled to end Complexity: O(n²) — slow for large datasets, simple to understand.
Selection Sort
Selection sort finds the minimum element in the unsorted portion and places it at the front of the unsorted section, one element per pass.
fn selection_sort(inout arr: List[Int]):
var n = len(arr)
for i in range(n):
var min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap minimum found with position i
var temp = arr[i]
arr[i] = arr[min_idx]
arr[min_idx] = temp
fn main():
var data = List[Int](29, 10, 14, 37, 13)
selection_sort(data)
for i in range(len(data)):
print(data[i], end=" ") # 10 13 14 29 37
Selection sort on [29, 10, 14, 37, 13]: Pass 1: find min(10) at idx 1 → swap with idx 0 → [10, 29, 14, 37, 13] Pass 2: find min(13) at idx 4 → swap with idx 1 → [10, 13, 14, 37, 29] Pass 3: find min(14) at idx 2 → no swap needed → [10, 13, 14, 37, 29] Pass 4: find min(29) at idx 4 → swap with idx 3 → [10, 13, 14, 29, 37] Done. Complexity: O(n²) — same speed as bubble sort, but makes fewer swaps.
Insertion Sort
Insertion sort builds a sorted subarray one element at a time, inserting each new element into its correct position in the already-sorted portion.
fn insertion_sort(inout arr: List[Int]):
var n = len(arr)
for i in range(1, n):
var key = arr[i]
var j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
fn main():
var data = List[Int](5, 2, 4, 6, 1, 3)
insertion_sort(data)
for i in range(len(data)):
print(data[i], end=" ") # 1 2 3 4 5 6
Insertion sort: think of sorting a hand of playing cards. Sorted: [2] Insert 7: [2, 7] Insert 1: [1, 2, 7] (1 slides to the front) Insert 5: [1, 2, 5, 7] Complexity: O(n²) worst case, O(n) best case (nearly-sorted data). Best choice for small arrays (<30 elements) or nearly-sorted data.
Merge Sort
Merge sort divides the array in half, sorts each half recursively, then merges the two sorted halves into one sorted result. It is the standard choice for stable, predictable sorting.
fn merge(inout arr: List[Int], left: Int, mid: Int, right: Int):
var left_part = List[Int]()
var right_part = List[Int]()
for i in range(left, mid + 1):
left_part.append(arr[i])
for i in range(mid + 1, right + 1):
right_part.append(arr[i])
var i = 0; var j = 0; var k = left
while i < len(left_part) and j < len(right_part):
if left_part[i] <= right_part[j]:
arr[k] = left_part[i]; i += 1
else:
arr[k] = right_part[j]; j += 1
k += 1
while i < len(left_part):
arr[k] = left_part[i]; i += 1; k += 1
while j < len(right_part):
arr[k] = right_part[j]; j += 1; k += 1
fn merge_sort(inout arr: List[Int], left: Int, right: Int):
if left < right:
var mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
merge(arr, left, mid, right)
fn main():
var data = List[Int](38, 27, 43, 3, 9, 82, 10)
merge_sort(data, 0, len(data) - 1)
for i in range(len(data)):
print(data[i], end=" ") # 3 9 10 27 38 43 82
Merge sort divide-and-merge diagram:
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43] [3, 9, 82, 10]
/ \ / \
[38] [27,43] [3,9] [82,10]
/ \ / \ / \
[27][43] [3] [9] [82] [10]
\ / \ / \ /
[27,43] [3,9] [10,82]
\ / /
[27,38,43] [3,9,10,82]
\ /
[3,9,10,27,38,43,82]
Complexity: O(n log n) — fast and predictable for all inputs.
Using Mojo's Built-In sort
from algorithm import sort
fn main():
var data = List[Int](5, 1, 4, 2, 8, 3)
sort(data) # in-place, highly optimized
for i in range(len(data)):
print(data[i], end=" ") # 1 2 3 4 5 8
Algorithm Comparison
Algorithm | Best | Average | Worst | Memory | Stable? ---------------|----------|----------|----------|--------|-------- Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes Merge Sort | O(n logn)| O(n logn)| O(n logn)| O(n) | Yes Mojo sort() | O(n logn)| O(n logn)| O(n logn)| O(logn)| — Stable = equal elements keep their original relative order.
Key Takeaways
Bubble, selection, and insertion sort are O(n²) — simple but slow for large datasets. Insertion sort is the best O(n²) algorithm for small or nearly-sorted arrays. Merge sort runs in O(n log n) for all cases and is stable, making it the default choice for general sorting. Mojo's built-in sort() uses an optimized algorithm and should be your first choice in production code. Study the manual implementations to understand the trade-offs; use the library function when performance matters.