Two examples of merge sort (merge sort) for Javascript sorting algorithm

  • 2020-03-30 02:34:31
  • OfStack

Merge sort is an effective sorting algorithm based on Merge operation. This algorithm is a very typical application of Divide and Conquer.

Merge sort method is to Merge two (or more than two) ordered tables into a new ordered table, that is, to sort the sequence into several sub-sequences, each sub-sequence is ordered. And then merge the ordered subsequence into a whole ordered sequence.

Merge sort is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. By combining the ordered subsequences, a completely ordered sequence is obtained. That is, make each subsequence ordered first, and then make the subsequence ordered between segments. 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 a space whose size is the sum of two sorted sequences, and the space is used to store the merged sequences
2. Set two Pointers, the initial position of which is respectively the starting position of two sorted sequences
3. Compare the elements to which the two Pointers point, select a relatively small element to put 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:




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:


<script type="text/javascript">
//Document. Write (" -- -- -- -- -- -- -- -- -- -- merge sort - only a stable complex sorting, time complexity for nlogn -- -- -- -- -- - <Br />" );
//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);
//The source source array
//Dest target array
//S initial subscript
//T target index
function mSort(source, dest, s, t) {
 var result = "";
 var m; //Take the median

 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);
      
      result += "<br /> The first " + ++count + " The result of sorting through is :";
   for (var n = 0; n < dest.length; n++) {
          result+= array[n] + ",";
        }
     
 }
 return result;
}


//Merge the two arrays in the order from small to large
//The source of the original array
//The array sorted by dest
//S first index
//M the second array is the following table
//The total length n
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 array to the end of 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>


Related articles: