# The Survival of Advanced Programmers The Use of Merge Sort

Let’s introduce the use of merge sort in detail, mainly analyze the examples in various language environments, please refer to it! ! !

### 1. Merge sort (Merge sort) is an efficient sorting algorithm based on the merge operation. This algorithm is a very typical application of Divide and Conquer.

As a typical algorithm application of the idea of ​​divide and conquer, the implementation of merge sort consists of two methods:

• Top-down recursion (all recursive methods can be rewritten with iteration, so there is a second method);
• bottom-up iteration;

In “Description of Data Structures and Algorithms in JavaScript”, the author gives a bottom-up iterative approach. But for the recursive method, the author believes that:

```However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

However, this is not feasible in JavaScript because the recursion depth of this algorithm is too deep for it.```

To be honest, I don’t quite understand this sentence. Does it mean that the memory of the JavaScript compiler is too small, and the recursion is too deep to cause memory overflow? I hope there is a god who can teach me.

Like selection sort, the performance of merge sort is not affected by the input data, but it performs much better than selection sort because it is always O(nlogn) time complexity. The tradeoff is that additional memory space is required.

### 2. Algorithm steps

1. Apply for space to be the sum of the two sorted sequences, and this space is used to store the merged sequence;

2. Set two pointers, the initial positions are the starting positions of the two sorted sequences;

3. Compare the elements pointed to by the two pointers, select a relatively small element into the merge space, and move the pointer to the next position;

4. Repeat step 3 until a pointer reaches the end of the sequence;

5. Copies all remaining elements of the other sequence directly to the end of the merged sequence.

### JavaScript instance

```function  mergeSort ( arr ) {   // use top-down recursion
var len = arr.length;
if (len < 2 ) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}```

### Python instance

```def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result```

### Go instance

```func mergeSort(arr []int) []int {
length := len(arr)
if length < 2 {
return arr
}
middle := length / 2
left := arr[0:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}

for len(left) != 0 {
result = append(result, left[0])
left = left[1:]
}

for len(right) != 0 {
result = append(result, right[0])
right = right[1:]
}

return result
}```

### Java instance

```public class MergeSort implements IArraySort {

@Override
public  int [] sort( int [] sourceArray) throws Exception {
// Copy arr without changing the parameter content
int [] arr = Arrays.copyOf(sourceArray, sourceArray.length);

if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);

int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);

return merge(sort(left), sort(right));
}

protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}

while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}

while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}

return result;
}

}```

### PHP example

```function mergeSort(\$arr)
{
\$len = count(\$arr);
if (\$len < 2) {
return \$arr;
}
\$middle = floor(\$len / 2);
\$left = array_slice(\$arr, 0, \$middle);
\$right = array_slice(\$arr, \$middle);
return merge(mergeSort(\$left), mergeSort(\$right));
}

function merge(\$left, \$right)
{
\$result = [];

while (count(\$left) > 0 && count(\$right) > 0) {
if (\$left[0] <= \$right[0]) {
\$result[] = array_shift(\$left);
} else {
\$result[] = array_shift(\$right);
}
}

while (count(\$left))
\$result[] = array_shift(\$left);

while (count(\$right))
\$result[] = array_shift(\$right);

return \$result;
}```

### C example

```int min(int x, int y) {
return x < y ? x : y;
}
void  merge_sort ( int arr[], int len)  {
int *a = arr;
int *b = ( int *) malloc (len * sizeof ( int ));
int seg, start;
for (seg = 1 ; seg < len; seg += seg) {
for (start = 0 ; start < len; start += seg * 2 ) {
int low = start, mid = min(start + seg, len), high = min(start + seg * 2 , len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int *temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}```

### C++ example

```template < typename T> // Both integers and floating-point numbers can be used, if you want to use the object (class), you must set the "less than" (<) operator function
void  merge_sort (T arr[], int len)  {
T *a = arr;
T *b = new T[len];
for ( int seg = 1 ; seg < len; seg += seg) {
for ( int start = 0 ; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len ), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
T *temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}```

### C# example

```public static List<int> sort(List<int> lst) {
if (lst.Count <= 1)
return lst;
int mid = lst.Count / 2;
List< int > left = new List< int >();   // Define the left List
List< int > right = new List< int >(); // Define the right List
// The following two loops divide lst into Left and right two List
for ( int i = 0 ; i < mid; i++)
for (int j = mid; j < lst.Count; j++)
left = sort(left);
right = sort(right);
return merge(left, right);
}
///  <summary>
/// Merge two sorted Lists
///  </summary>
///  <param > Left List </param>
///  <param > Right List </param>
///  <returns> </returns>
static List< int > merge ( List< int > left, List< int > right ) {
List<int> temp = new List<int>();
while (left.Count > 0 && right.Count > 0) {
if (left[0] <= right[0]) {
left.RemoveAt(0);
} else {