Sorting is one of the most fundamental operations in computer science. Many problems become easier once the data is sorted — binary search, duplicate detection, and merge operations all require sorted input. In this article, you will learn the most important sorting algorithms, their trade-offs, and when to use each one.
We show every example in Kotlin, Python, and Go.
Why Sorting Matters
Sorting unlocks other algorithms:
- Binary search requires sorted data — O(log n) instead of O(n)
- Two pointers on sorted arrays solve many problems efficiently
- Duplicate detection becomes O(n) on sorted data (just compare neighbors)
- Merge operations are faster on sorted inputs
Interviewers often ask: “Can you sort the input first to simplify the problem?”
Simple Sorts: O(n^2)
These sorts are easy to understand but slow for large inputs.
Bubble Sort
Compare adjacent elements and swap if they are in the wrong order. Repeat until no swaps are needed.
Python:
def bubble_sort(nums):
n = len(nums)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
swapped = True
if not swapped:
break # Already sorted
return nums
Time: O(n^2) worst and average, O(n) best (already sorted). Space: O(1). Stable: Yes.
Selection Sort
Find the minimum element and put it at the front. Repeat for the remaining elements.
Kotlin:
fun selectionSort(nums: IntArray): IntArray {
for (i in nums.indices) {
var minIndex = i
for (j in i + 1 until nums.size) {
if (nums[j] < nums[minIndex]) {
minIndex = j
}
}
val temp = nums[i]
nums[i] = nums[minIndex]
nums[minIndex] = temp
}
return nums
}
Time: O(n^2) always. Space: O(1). Stable: No.
Insertion Sort
Build the sorted array one element at a time. Take each element and insert it into its correct position in the already-sorted part.
Go:
func insertionSort(nums []int) []int {
for i := 1; i < len(nums); i++ {
key := nums[i]
j := i - 1
for j >= 0 && nums[j] > key {
nums[j+1] = nums[j]
j--
}
nums[j+1] = key
}
return nums
}
Time: O(n^2) worst, O(n) best (nearly sorted). Space: O(1). Stable: Yes.
Insertion sort is actually fast for small arrays (n < 20). Many real-world sorting implementations switch to insertion sort for small subarrays.
Merge Sort: O(n log n), Stable
Merge sort uses divide and conquer: split the array in half, sort each half recursively, then merge the two sorted halves.
Python:
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Kotlin:
fun mergeSort(nums: List<Int>): List<Int> {
if (nums.size <= 1) return nums
val mid = nums.size / 2
val left = mergeSort(nums.subList(0, mid))
val right = mergeSort(nums.subList(mid, nums.size))
return merge(left, right)
}
fun merge(left: List<Int>, right: List<Int>): List<Int> {
val result = mutableListOf<Int>()
var i = 0
var j = 0
while (i < left.size && j < right.size) {
if (left[i] <= right[j]) {
result.add(left[i++])
} else {
result.add(right[j++])
}
}
while (i < left.size) result.add(left[i++])
while (j < right.size) result.add(right[j++])
return result
}
Go:
func mergeSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}
mid := len(nums) / 2
left := mergeSort(nums[:mid])
right := mergeSort(nums[mid:])
return mergeSorted(left, right)
}
func mergeSorted(left, right []int) []int {
result := make([]int, 0, len(left)+len(right))
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] <= right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
Time: O(n log n) always. Space: O(n) for the temporary arrays. Stable: Yes.
Merge sort is the go-to when you need a stable sort with guaranteed O(n log n). Python’s sorted() uses Timsort, which is a hybrid of merge sort and insertion sort.
Quick Sort: O(n log n) Average, In-Place
Quick sort picks a pivot element, partitions the array into elements less than the pivot and elements greater than the pivot, then sorts each partition recursively.
Python:
def quick_sort(nums, low=0, high=None):
if high is None:
high = len(nums) - 1
if low < high:
pivot_index = partition(nums, low, high)
quick_sort(nums, low, pivot_index - 1)
quick_sort(nums, pivot_index + 1, high)
return nums
def partition(nums, low, high):
pivot = nums[high] # Choose last element as pivot
i = low - 1
for j in range(low, high):
if nums[j] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[high] = nums[high], nums[i + 1]
return i + 1
Kotlin:
fun quickSort(nums: IntArray, low: Int = 0, high: Int = nums.size - 1) {
if (low < high) {
val pivotIndex = partition(nums, low, high)
quickSort(nums, low, pivotIndex - 1)
quickSort(nums, pivotIndex + 1, high)
}
}
fun partition(nums: IntArray, low: Int, high: Int): Int {
val pivot = nums[high]
var i = low - 1
for (j in low until high) {
if (nums[j] <= pivot) {
i++
val temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
}
val temp = nums[i + 1]
nums[i + 1] = nums[high]
nums[high] = temp
return i + 1
}
Go:
func quickSort(nums []int, low, high int) {
if low < high {
pivotIndex := partition(nums, low, high)
quickSort(nums, low, pivotIndex-1)
quickSort(nums, pivotIndex+1, high)
}
}
func partition(nums []int, low, high int) int {
pivot := nums[high]
i := low - 1
for j := low; j < high; j++ {
if nums[j] <= pivot {
i++
nums[i], nums[j] = nums[j], nums[i]
}
}
nums[i+1], nums[high] = nums[high], nums[i+1]
return i + 1
}
Time: O(n log n) average, O(n^2) worst case (already sorted with bad pivot). Space: O(log n) for the recursion stack. Stable: No.
Quick sort is usually faster than merge sort in practice because it has better cache performance and sorts in-place.
Counting Sort: O(n + k)
When values are integers in a small range [0, k], counting sort beats comparison-based sorts.
Python:
def counting_sort(nums, max_val):
count = [0] * (max_val + 1)
for num in nums:
count[num] += 1
result = []
for val in range(max_val + 1):
result.extend([val] * count[val])
return result
# Example: sort ages (0-150)
ages = [25, 30, 25, 18, 30, 22]
sorted_ages = counting_sort(ages, 150) # O(n + 150) = O(n)
Time: O(n + k) where k is the range of values. Space: O(k). Stable: Yes.
Use counting sort when the range of values k is small relative to n.
Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable | In-Place |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | Yes |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | No |
Which Sort to Use
In interviews, say this:
- Default choice: Use your language’s built-in sort — it is optimized and O(n log n)
- Need stability: Merge sort or Timsort (Python default)
- Memory constrained: Quick sort (in-place) or heap sort
- Small array: Insertion sort
- Integer values in small range: Counting sort or radix sort
Built-in sorts:
# Python: Timsort — O(n log n), stable
nums = [3, 1, 4, 1, 5]
nums.sort() # in-place
sorted_nums = sorted(nums) # returns new list
// Kotlin: Timsort — O(n log n), stable
val nums = mutableListOf(3, 1, 4, 1, 5)
nums.sort() // in-place
val sorted = listOf(3, 1, 4, 1, 5).sorted() // returns new list
// Go: Pattern-defeating quicksort — O(n log n)
import "sort"
nums := []int{3, 1, 4, 1, 5}
sort.Ints(nums) // in-place
Interview Problems
Sort Colors (Dutch National Flag)
Sort an array of 0s, 1s, and 2s in one pass.
Python:
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
# Time: O(n), Space: O(1)
Merge Intervals
Given a list of intervals, merge all overlapping intervals. Sort first, then merge.
Python:
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # Sort by start time
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# Time: O(n log n) for sorting, Space: O(n)
Common Mistakes
Not knowing the difference between stable and unstable sorts. A stable sort preserves the relative order of equal elements. This matters when sorting by multiple keys.
Using O(n^2) sorts in production. Bubble sort and selection sort should only be used for tiny arrays or educational purposes.
Forgetting that quick sort can be O(n^2). With a bad pivot (like always picking the first element on an already sorted array), quick sort degrades. Use randomized pivot selection.
Not knowing your language’s built-in sort. In interviews, you should use the built-in sort unless asked to implement one.
What’s Next?
Now that you understand sorting, the next article covers Binary Search — the most important algorithm that works on sorted data. You will learn templates, search on answer, and rotated array problems.
Next: DSA Tutorial #13: Binary Search
Full series: DSA from Zero to Interview Ready