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.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 = "")

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

  • The checked input is passed directly as an R vector: merge_sort(c(5, 1, 4, 2, 8)).
  • merge_sort <- function(values) returns a new sorted vector; it does not sort the caller's vector in place.
  • The base case is if (length(values) <= 1) return(values).
  • R indexing is 1-based, so mid <- floor(length(values) / 2) splits this five-value input into values[1:2] and values[3:5].
  • The recursive calls are left <- merge_sort(values[1:mid]) and right <- merge_sort(values[(mid + 1):length(values)]).
  • merged <- c() starts an empty vector for the merge result.
  • The merge cursors start at i <- 1; j <- 1.
  • The main merge loop is while (i <= length(left) && j <= length(right)).
  • The comparison is left[i] <= right[j]; the left side wins ties in this source.
  • Appends use vector concatenation, for example merged <- c(merged, left[i]).
  • Leftover values are appended with slices: left[i:length(left)] or right[j:length(right)].

Replay steps

input:       [5, 1, 4, 2, 8]
split:       left [5, 1], right [4, 2, 8]
sorted:      left [1, 5], right [2, 4, 8]
merged:      [1, 2, 4, 5, 8]
  • The final cat call combines "[", paste(arr, collapse = ", "), and a closing bracket string that contains the newline, so it prints [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.