非原地分区

  1. function merge(left, right) {
  2.   var target = [];
  4.   while (left.length > 0 && right.length > 0) {
  5.     target.push(left[0] < right[0] ? left.shift() : right.shift());
  6.   }
  8.   return target.concat(left, right);
  9. }
  11. function sortArray(nums) {
  12.   if (nums.length <= 1) {
  13.     return nums;
  14.   }
  16.   var mid = Math.floor(nums.length / 2);
  17.   var left = nums.slice(0, mid);
  18.   var right = nums.slice(mid);
  20.   return merge(sortArray(left), sortArray(right));
  21. }

原地分区

  1. function partition(nums, start, end) {
  2.   if (start >= end) {
  3.     return;
  4.   }
  6.   var mid = Math.floor((start + end) / 2);
  7.   partition(nums, start, mid);
  8.   partition(nums, mid + 1, end);
  10.   merge(nums, start, mid, end);
  11. }
  13. function merge(nums, start, mid, end) {
  14.   var i = start;
  15.   var j = mid + 1;
  17.   var target = [];
  19.   while (i <= mid && j <= end) {
  20.     if (nums[i] > nums[j]) {
  21.       target.push(nums[j++]);
  22.     } else {
  23.       target.push(nums[i++]);
  24.     }
  25.   }
  27.   while (i <= mid) {
  28.     target.push(nums[i++]);
  29.   }
  30.   while (j <= end) {
  31.     target.push(nums[j++]);
  32.   }
  34.   for (var k = 0; k < target.length; k++) {
  35.     nums[start + k] = target[k];
  36.   }
  37. }
  39. function sortArray(nums) {
  40.   if (nums.length <= 1) {
  41.     return nums;
  42.   }
  44.   partition(nums, 0, nums.length - 1);
  46.   return nums;
  47. }

总结

  • 原理：分而治之
  • 时间复杂度：O(nlogn)