# Merge Sorted Array

## Core tech of MergeSort

Merge is the core technology of MergeSort, that is why it was named MergeSort.

```
convert input array -> left_part and right_part
left_sorted_part = MergeSort(left_part)
right_sorted_part = MergeSort(right_part)
Merge(left_sorted_part, right_sorted_part)
```

## Merging

- set
`t`

the end of`result array`

- taking one (
`l`

) from the end of`left_sorted_part`

- taking one (
`r`

) from the end of`right_sorted_part`

- find the larger(
`g`

) one in`l`

and`r`

- put
`g`

at position`t`

of`result array`

- loop until
`t`

reach the bottom of`result array`

When `result array`

is an empty array,
it is passable to copy from the beginning of `left_sorted_part`

and `right_sorted_part`

.

In this problem, however, we have to copy from end to beginning due to that `left_sorted_part`

and `result array`

are sharing the same array.

### Source code *Read on Github*

```
1 public class Solution {
2
3 int safe(int X[], int i){
4 if(i < 0) return Integer.MIN_VALUE;
5
6 return X[i];
7 }
8
9 public void merge(int A[], int m, int B[], int n) {
10
11 int t = A.length - 1;
12
13 int pa = m - 1;
14 int pb = n - 1;
15
16 while(t >= 0){
17
18 int a = safe(A, pa);
19 int b = safe(B, pb);
20
21 if(a > b){
22 A[t] = a;
23 pa--;
24 }else{
25 A[t] = b;
26 pb--;
27 }
28
29 t--;
30 }
31
32 }
33 }
```