2 Examples of Javascript Sorting Algorithm Merge Sort (Merge Sort)_Basic Knowledge

Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer).

Merge sorting method is to merge two (or more) ordered lists into a new ordered list, that is, the sequence to be sorted is divided into several subsequences, and each subsequence is ordered. Then merge the ordered subsequences into the overall ordered sequence.

Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer). Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a 2-way merge.

The process of merge operation is as follows:

1. Apply for space so that its size is the sum of the two sorted sequences. This space is used to store the merged sequence
2. Set two pointers, the initial positions of which are the two sorted sequences. Starting position
3. Compare the elements pointed to by the two pointers, select a relatively small element and put it into the merge space, and move the pointer to the next position
4. Repeat step 3 until a certain pointer reaches the end of the sequence
5. Copy all remaining elements of the other sequence directly to the end of the merged sequence

Example 1:

Copy code The code is as follows:

/**
* Merge operation (merge), also called merge algorithm, refers to the operation of merging two sorted sequences into one sequence.
* The merge sort algorithm relies on merge operations.
*
* The process of merging operation is as follows:
*
* 1. Apply for space so that its size is the sum of two sorted sequences. 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 the relatively small element and put it 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 remaining elements of the other sequence directly to the end of the merged sequence
*
*/

function mergeSort(items) {
if (items.length 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 if ( left[il]                                result.push(left[il]); >                                                           return result.concat(left.slice(il)) .concat(right.slice(ir)); = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];

mergeSort(arr);



Example 2:





Copy code

The code is as follows: