Many useful algorithms have a recursive structure. A common pattern that comes up is solving a problem by first breaking down the initial problem into two or more sub-problems which can be solved recursively, and then finally combining the two sub-problems together. Note that not all problems can be solved in this way
Divide and Conquer
An algorithm that solves a problem by recursively solving subproblems and then re-combining them is said to be a divide and conquer algorithm.
is Correct
Given an array
A
and indices
left_idx
,
split_idx
,
right_idx
such that the subarrays
A
[
left_idx
,
.
.
.
,
split_idx
]
,
A
[
split_idx + 1
,
.
.
.
,
right_idx
]
are already sorted in ascending order then after merge sort has terminated, then the subarray
A
[
left_idx
,
.
.
.
,
right_idx
]
is sorted in ascending order
merge_sort
is Correct
Given any list, merge sort correctly sorts it in place