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.scala 
object Main {
	def mergeSort(values: List[Int]): List[Int] = {
		if (values.length <= 1) return values
		val (leftRaw, rightRaw) = values.splitAt(values.length / 2)
		val left = mergeSort(leftRaw)
		val right = mergeSort(rightRaw)
		merge(left, right)
	}

	def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
		case (Nil, _) => right
		case (_, Nil) => left
		case (l :: ls, r :: rs) =>
			if (l <= r) l :: merge(ls, right) else r :: merge(left, rs)
	}
	def main(args: Array[String]): Unit = {
		val arr = List(5, 1, 4, 2, 8)
		println(mergeSort(arr).mkString("[", ", ", "]"))
	}
}

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

  • This checked Scala source uses List[Int], not Array[Int]: val arr = List(5, 1, 4, 2, 8).
  • mergeSort(values: List[Int]): List[Int] produces a sorted List[Int] without mutating the input list; base and leftover cases can return existing list values directly.
  • The base case if (values.length <= 1) return values stops recursion for empty and single-element lists.
  • val (leftRaw, rightRaw) = values.splitAt(values.length / 2) splits the list into two list halves, then val left and val right hold the recursive sorted results.
  • merge(left, right) uses pattern matching: Nil returns the leftover other list, and l :: ls / r :: rs exposes each front value.
  • The comparison if (l <= r) keeps equal values from the left side first, then builds the output with :: cons cells.
  • The trace shows [5, 1, 4, 2, 8] splitting into [5, 1] and [4, 2, 8], those halves sorting to [1, 5] and [2, 4, 8], then merging to [1, 2, 4, 5, 8].
  • println(mergeSort(arr).mkString("[", ", ", "]")) prints the final 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.