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 thinks:
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.
-
Apply for space so that its size is the sum of the two sorted sequences, and this space is used to store the merged sequence;
-
Set two pointers, the initial positions are the starting positions of the two sorted sequences;
-
Compare the elements pointed to by the two pointers, select a relatively small element to put into the merge space, and move the pointer to the next position;
-
Repeat step 3 until a pointer reaches the end of the sequence;
-
Copy all remaining elements of the other sequence directly to the end of the merged sequence.
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;
}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 resultfunc 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
}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;
}
}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;
}void merge(vector<int>& arr, int l, int mid, int r) {
int index = 0;
int ptrL = l;
int ptrR = mid;
static vector<int>tempary;
if (arr.size() > tempary.size()) {
tempary.resize(arr.size());
}
while (ptrL != mid && ptrR != r) {
if (arr[ptrL] < arr[ptrR]) {
tempary[index++] = arr[ptrL++];
} else {
tempary[index++] = arr[ptrR++];
}
}
while (ptrL != mid) {
tempary[index++] = arr[ptrL++];
}
while (ptrR != r) {
tempary[index++] = arr[ptrR++];
}
copy(tempary.begin(), tempary.begin() + index, arr.begin() + l);
}
void mergeSort(vector<int>& arr, int l, int r) { // sort the range [l, r) in arr
if (r - l <= 1) {
return;
}
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid, r);
merge(arr, l, mid, r);
}