$./mergesort
preset:
2 step/s
# algorithm
1mergeSort(A, left, right)
2begin
3 if left < right then
4 mid ← (left + right) / 2
5 mergeSort(A, left, mid)
6 mergeSort(A, mid+1, right)
7 merge(A, left, mid, right)
8end
9
10merge(A, left, mid, right)
11begin
12 L ← A[left..mid]
13 R ← A[mid+1..right]
14 i ← 0; j ← 0; k ← left
15 while i < |L| and j < |R| do
16 if L[i] ≤ R[j] then
17 A[k] ← L[i]; i ← i+1
18 else
19 A[k] ← R[j]; j ← j+1
20 k ← k+1
21 copy remaining L to A
22 copy remaining R to A
23end
# array visualization
38
0
27
1
43
2
3
3
9
4
82
5
10
6
mid comparing copying merged active
# variables
left
—
mid
—
right
—
k
—
# merge pointers
i (left)
—
j (right)
—
# left array (L)
empty
# right array (R)
empty
# call stack (recursion)
empty
# current action
select a preset and click "run" to begin...
# array state
[38,27,43,3,9,82,10]