1.5 Merge Sort
Category Algorithm
Merge sort is an efficient sorting algorithm based on the merge operation. This algorithm is a very typical application of the divide and conquer method.
As a typical application of the divide and conquer algorithm, the implementation of merge sort has two methods:
Top-down recursion (all recursive methods can be rewritten in iteration, hence the second method);
Bottom-up iteration;
In "Data Structures and Algorithms in JavaScript," the author presents the bottom-up iterative method. However, for the recursive method, the author believes:
>
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
But to be honest, I don't quite understand this sentence. Does it mean that the JavaScript compiler has too little memory, and deep recursion can easily cause a memory overflow? I hope someone can enlighten 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 always has a time complexity of O(nlogn). The cost is the need for additional memory space.
2. Algorithm Steps
-
Allocate space, with a size equal to the sum of the two sorted sequences, which is used to store the merged sequence;
-
Set two pointers, initially positioned at the starting positions of the two sorted sequences;
-
Compare the elements pointed to by the two pointers, choose the smaller element and place it into the merge space, and move the pointer to the next position;
-
Repeat step 3 until one of the pointers reaches the end of the sequence;
-
Directly copy all the remaining elements of the other sequence to the end of the merged sequence.
3. Animated Demonstration
Code Implementation
JavaScript
Example
function mergeSort(arr) { // Using top-down recursive method
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
Example
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
Example
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
Example
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy arr to avoid changing the input array
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (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);
}
**Recursive version:**
## Example
void merge_sort_recursive(int arr[], int reg[], int start, int end) { if (start >= end) return; int len = end - start, mid = (len >> 1) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(arr, reg, start1, end1); merge_sort_recursive(arr, reg, start2, end2); int k = start; while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; while (start1 <= end1) reg[k++] = arr[start1++]; while (start2 <= end2) reg[k++] = arr[start2++]; for (k = start; k <= end; k++) arr[k] = reg[k]; }
void merge_sort(int arr[], const int len) { int reg[len]; merge_sort_recursive(arr, reg, 0, len - 1); }
### C++
**Iterative version:**
## Example
template<typename T> // Integers or floating points can be used, if using objects (class), the "less than" (<) operator must be defined 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; }
**Recursive version:**
## Example
void Merge(vector<int> &Array, int front, int mid, int end) { // preconditions: // Array[front...mid] is sorted // Array[mid+1 ... end] is sorted // Copy Array[front ... mid] to LeftSubArray // Copy Array[mid+1 ... end] to RightSubArray vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1); vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1); int idxLeft = 0, idxRight = 0; LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max()); RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max()); // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i] for (int i = front; i <= end; i++) {
English: If the first element of the left is less than the first element of the right, then shift left; otherwise, shift right. End if. End. The final result is the sum of left and right. }.call merge(list[0...pivot]), merge(list[pivot..-1]) End
>
Reference address:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/5.mergeSort.md
https://zh.wikipedia.org/wiki/Merge_sort
##
-
** ees
** 429***[email protected]
** [Reference address](https://www.cnblogs.com/chengxiao/p/6194356.html)
**Divide and Conquer**
You can see that this structure is very similar to a complete binary tree. The merge sort in this article is implemented recursively (it can also be implemented iteratively). The "divide" phase can be understood as the process of recursively dividing the sub-sequence, with a recursion depth of log.
**Merge adjacent ordered sub-sequences**
Let's look at the "conquer" phase again. We need to merge two already ordered sub-sequences into one ordered sequence. For example, in the last merge of the above figure, we need to merge the two already ordered sub-sequences [4,5,7,8] and [1,2,3,6] into the final sequence [1,2,3,4,5,6,7,8]. Let's see the implementation steps.
import java.util.Arrays;
/**
- Created by chengxiao on 2016/12/8. */ public class MergeSort { public static void main(String []args){ int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ int []temp = new int[arr.length];//Before sorting, create a temporary array with the same length as the original array to avoid frequent space allocation in recursion sort(arr,0,arr.length-1,temp); } private static void sort(int[] arr,int left,int right,int []temp){ if(left<right){ int mid = (left+right)/2; sort(arr,left,mid,temp);//Left merge sort, make the left sub-sequence ordered sort(arr,mid+1,right,temp);//Right merge sort, make the right sub-sequence ordered merge(arr,left,mid,right,temp);//Merge two ordered sub-arrays } } private static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left;//Left sequence pointer int j = mid+1;//Right sequence pointer int t = 0;//Temporary array pointer while (i<=mid && j<=right){ if(arr[i]<=arr[j]){ temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } while(i<=mid){//Fill the remaining elements on the left into temp temp[t++] = arr[i++]; } while(j<=right){//Fill the remaining elements on the right into temp temp[t++] = arr[j++]; } t = 0; //Copy all elements from temp to the original array while(left <= right){ arr[left++] = temp[t++]; } } }
** ees
** 429***[email protected]
** [Reference address](https://www.cnblogs.com/chengxiao/p/6194356.html)
-
** kezhuoquan
** kez***[email protected]
Rust version:
fn merge_sort<T: Ord + Debug + Copy>(array: &mut [T], start: usize, end: usize) {
if start >= end {
return;
}
let mid = start + (end - start) / 2;
merge_sort(array, start, mid);
merge_sort(array, mid + 1, end);
merge(array, start, end);
}
fn merge<T: Ord + Debug + Copy>(array: &mut [T], start: usize, end: usize) {
println!("{array:?}");
let mut temp_array = Vec::with_capacity(end - start + 1);
for i in start..=end {
temp_array.push(array[i]);
}
let new_start = 0;
let new_end = temp_array.len() - 1;
let new_mid = (new_end - new_start) / 2;
let mut left_index = new_start;
let mut right_index = new
// Method Three: Sorting and merging the split arrays
private void Merge(float[] arr, float[] temp, int left, int mid, int right)
{
int l_pos = left; // The first unsorted element of the left half
int r_pos = mid + 1; // The first unsorted element of the right half
int pos = left; // The starting index of the auxiliary array
while (l_pos <= mid && r_pos <= right)
{
if (arr[l_pos] < arr[r_pos]) // Compare each one by one
{
temp[pos++] = arr[l_pos++]; // If the element in the left area is smaller, put it in the first position of the auxiliary array, and then move the index of the left area and the auxiliary array one step back
}
else temp[pos++] = arr[r_pos++]; // If the element in the right area is smaller, put it in the auxiliary array, and move the index back
} // Exit the loop means that one side of the left and right has been completely put into the auxiliary array
while (l_pos <= mid)
{
temp[pos++] = arr[l_pos++]; // If the index of the left area has not reached the maximum, it means there is a surplus, directly copy all to the end of the auxiliary array
}
while (r_pos <= right)
{
temp[pos++] = arr[r_pos++]; // If the index of the right area has not reached the maximum, it means there is a surplus, directly copy all to the end of the auxiliary array
}
while (left <= right)
{
arr[left] = temp[left]; // From the first index to the last index, copy all the elements of the auxiliary array to the original array
left++;
}
} }
** Night of the Moon
* yan**[email protected]
-
** _
* 224**[email protected]
js version:
const mergeSort = arr => {
if (arr.length === 1) {
return arr
}
const mid = Math.floor(arr.length / 2)
return ((left, right) => {
const result = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
result.push(left[i] > right[j] ? right[j++] : left[i++])
}
while (i < left.length) {
result.push(left[i++])
}
while (j < right.length) {
result.push(right[j++])
}
return result
})(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
** _
* 224**[email protected]
** Click here to share notes
-
-
-
-1.0 Top 10 Classic Sorting Algorithms
- 1.5 Merge Sort