Sorting

Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.kt 
fun mergeSort(values: List<Int>): List<Int> {
	if (values.size <= 1) return values
	val mid = values.size / 2
	val left = mergeSort(values.subList(0, mid))
	val right = mergeSort(values.subList(mid, values.size))
	val merged = mutableListOf<Int>()
	var i = 0
	var j = 0
	while (i < left.size && j < right.size) {
		if (left[i] <= right[j]) merged.add(left[i++]) else merged.add(right[j++])
	}
	merged.addAll(left.drop(i))
	merged.addAll(right.drop(j))
	return merged
}

fun main() {
	val arr = listOf(5, 1, 4, 2, 8)
	println(mergeSort(arr).joinToString(prefix = "[", postfix = "]"))
}

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

  • Time: O(n log n)
  • Space: O(n)
  • Stable: yes

Implementation notes

  • Kotlin stores the input in val arr = listOf(5, 1, 4, 2, 8), a val binding to a read-only List<Int>; the source never mutates arr.
  • The recursive signature is mergeSort(values: List<Int>): List<Int>. if (values.size <= 1) return values is the base case, while non-base calls build and return a new merged list.
  • Splitting uses values.subList(0, mid) and values.subList(mid, values.size); those list views are passed into recursive calls before merging.
  • The merge buffer is val merged = mutableListOf<Int>(). Cursor indexes i and j are mutable var Int values that advance with left[i++] and right[j++].
  • if (left[i] <= right[j]) uses Int comparison and takes the left value on ties, preserving stable ordering for equal values.
  • Remaining elements are appended with merged.addAll(left.drop(i)) and merged.addAll(right.drop(j)); drop creates suffix lists for the leftovers.
  • The trace shows [5, 1, 4, 2, 8] split into [5, 1] and [4, 2, 8], sorted to [1, 5] and [2, 4, 8], then merged into [1, 2, 4, 5, 8].
  • println(mergeSort(arr).joinToString(prefix = "[", postfix = "]")) formats the returned list as [1, 2, 4, 5, 8].
divide and conquer Each recursive call solves a smaller sorted subproblem.
merge step Two sorted halves are combined by repeatedly taking the smaller front item.