In computer science, merge sort (also normally spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. A detailed description and analysis of bottom-up mergesort looked in a report by Goldstine and von Neumann as early as 1948.

repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. divide the unsorted list into N sublists, each containing one component (a list of one component is considered sorted).

```
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int end = m + n - 1;
m -= 1;
n -= 1;
while (m >= 0 && n >= 0) {
if (A[m] > B[n])
A[end--] = A[m--];
else
A[end--] = B[n--];
}
while (m >= 0)
A[end--] = A[m--];
while (n >= 0)
A[end--] = B[n--];
}
};
```