Sorting

Merge Sort (Top-Down)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this R DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.R 
merge_sort <- function(values) {
	if (length(values) <= 1) return(values)
	mid <- floor(length(values) / 2)
	left <- merge_sort(values[1:mid])
	right <- merge_sort(values[(mid + 1):length(values)])
	merged <- c()
	i <- 1; j <- 1
	while (i <= length(left) && j <= length(right)) {
		if (left[i] <= right[j]) { merged <- c(merged, left[i]); i <- i + 1 }
		else { merged <- c(merged, right[j]); j <- j + 1 }
	}
	if (i <= length(left)) merged <- c(merged, left[i:length(left)])
	if (j <= length(right)) merged <- c(merged, right[j:length(right)])
	merged
}

arr <- merge_sort(c(5, 1, 4, 2, 8))
cat("[", paste(arr, collapse = ", "), "]
", sep = "")

Complexity

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

Implementation notes

  • Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
  • The implementation is intentionally compact for learning and replay, not a production sorting utility.
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.