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.sh 
#!/usr/bin/env bash
set -euo pipefail

merge_sort() {
	local values=("$@")
	local n=${#values[@]}
	if ((n <= 1)); then
		printf '%s\n' "${values[@]}"
		return
	fi

	local mid=$((n / 2))
	local left=("${values[@]:0:mid}")
	local right=("${values[@]:mid}")
	local sorted_left=()
	local sorted_right=()
	mapfile -t sorted_left < <(merge_sort "${left[@]}")
	mapfile -t sorted_right < <(merge_sort "${right[@]}")

	local i=0
	local j=0
	while ((i < ${#sorted_left[@]} && j < ${#sorted_right[@]})); do
		if ((sorted_left[i] <= sorted_right[j])); then
			printf '%s\n' "${sorted_left[i]}"
			i=$((i + 1))
		else
			printf '%s\n' "${sorted_right[j]}"
			j=$((j + 1))
		fi
	done
	while ((i < ${#sorted_left[@]})); do
		printf '%s\n' "${sorted_left[i]}"
		i=$((i + 1))
	done
	while ((j < ${#sorted_right[@]})); do
		printf '%s\n' "${sorted_right[j]}"
		j=$((j + 1))
	done
}

arr=(5 1 4 2 8)
mapfile -t arr < <(merge_sort "${arr[@]}")
printf '['
sep=''
for v in "${arr[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

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

  • arr=(5 1 4 2 8) is the pinned Bash indexed array. The script now sorts it with merge_sort, not external sort.
  • merge_sort() copies its arguments into a local array with local values=("$@"), then uses n=${#values[@]} as the base-case size.
  • For more than one value, mid=$((n / 2)) splits local arrays with Bash slice syntax: left=("${values[@]:0:mid}") and right=("${values[@]:mid}").
  • Bash functions cannot return arrays directly. Each recursive call prints one sorted value per line, and mapfile -t sorted_left < <(merge_sort ...) captures that stdout stream back into a local array.
  • That stream shape is intentionally simple for these pinned integers: one number per line, no spaces inside values.
  • The merge loop compares numbers with Bash arithmetic evaluation: ((sorted_left[i] <= sorted_right[j])).
  • The <= branch chooses the left value first on ties, so equal values keep their left-before-right order.
  • Remaining left or right values are printed by the two cleanup while loops.

Replay steps

start: [5, 1, 4, 2, 8]
split: left [5, 1], right [4, 2, 8]
sort:  left [1, 5], right [2, 4, 8]
merge: [1, 2, 4, 5, 8]
  • Final output uses the same formatter as nearby Bash sorting lessons: printf '[', sep='', for v in "${arr[@]}", printf '%s%d' "$sep" "$v", then printf ']\n'.
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.