When we try to divide an array into 2 halves, we need to specify 3 parameters:
- Which index does the left array start with? begin
- Which index does the right array start with? mid
- Which index does the right array end? end
So naturally, the array can be divided into two halves of
[0...mid-1] and [mid...end]
Note that initially, the begin of left array is 0, and the end of the right array is (the size of the array - 1)
Mid
Mid = (end + begin) / 2;
Begin
In left array, 'begin' remains,
begin = begin;
While in right array,
begin = mid;
End
In left array,
end = mid - 1;
in Right array,
end = end;
In all, we can write a function as follow to divide any array:
void Array_Division(vector<int>& arr, int begin, int mid, int end) {
//for left array
Array_Division(arr, begin, (mid-1+begin)/2, mid-1);
//for right array
Array_Division(arr, mid, (end+mid)/2, end);
}
