Merge sort is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer.
Merge sorting method is to merge two (or more than two) ordered tables into a new ordered table, that is, divide the sequence to be sorted into several subsequences, each subsequence is ordered. Then the ordered subsequences are combined into the overall ordered sequence.
Merge sorting is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. Merge the ordered subsequences to obtain a completely ordered sequence; that is, make each subsequence first order, and then make the subsequence segments order. If two ordered tables are merged into one ordered table, it is called 2-way merge.
The merge operation process is as follows:
1. Apply for space so that its size is the sum of two sorted sequences, which is used to store the merged sequences
2. Set two pointers, the initial position is the starting position of the two sorted sequences respectively
3. Compare the elements pointed to by two pointers, select relatively small elements and put them 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. Copy all the remaining elements of another sequence directly to the end of the merge sequence
Example 1:
The code copy is as follows:
/**
* Merge, also known as a merge algorithm, refers to the operation of combining two sorted sequences into one sequence.
* The merge sorting algorithm depends on the merge operation.
*
* The merge operation process is as follows:
*
* 1. Apply for space so that its size is the sum of two sorted sequences, which is used to store the merged sequences
* 2. Set two pointers, the initial positions are the starting positions of the two sorted sequences respectively
* 3. Compare the elements pointed to by the two pointers, select relatively small elements and put them 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. Copy all the remaining elements of another sequence directly to the end of the merged sequence
*
*/
function mergeSort(items) {
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
function merge(left, right) {
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)) .concat(right.slice(ir));
}
}
// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
mergeSort(arr);
Example 2:
The code copy is as follows:
<script type="text/javascript">
//document.write("-------------------------------------------------------------------------------------------------------------------------------------);
//var array = new Array(12, 25, 32, 16, 18, 27, 59, 69, 36);
var count = 0;
//Call the sort method to sort
//mSort(array, array, 0, array.length - 1);
//source source array
//dest target array
//s Start subscript
//tTarget subscript
function mSort(source, dest, s, t) {
var result = "";
var m; //Take the intermediate value
var dest2 = new Array();
if (s == t) {
dest[s] = source[s];
}
else {
m = Math.floor((s + t) / 2);
mSort(source, dest2, s, m);
mSort(source, dest2, m+1, t);
merge(dest2, dest, s, m, t);
/* Output result*/
result += "<br />Thread" + ++count + "The result of the ordering of the pass is:";
for (var n = 0; n < dest.length; n++) {
result+= array[n] + ",";
}
/* The output result ends*/
}
return result;
}
/* The output result ends*/
//Fused two arrays in order from small to large
//source original array
//Dest sorted array
//sThe first subscript
//m The following table of the second array
//nTotal length
function merge(source, dest, s, m, n) {
for (var j = m+1, k = s; j <= n && s <= m; k++) {
if (source[s] < source[j]) {
dest[k] = source[s++];
}
else {
dest[k] = source[j++];
}
}
//Add the remaining ordered arrays to the end of the dest
if (s <= m) {
for (var l = 0; l <= m - s; l++) {
dest[k + l] = source[s+l];
}
}
if (j <= n) {
for (var l = 0; l <= n - j; l++) {
dest[k + l] = source[j+l];
}
}
}
//document.write("<br /><br />")
</script>