11 Quick sort (with 2 partition schemes) and merge sort in JavaScript

quicksort.js

// 实现基于两种不同原地分区方式的快排
function quicksort(arr){
  qs(arr, 0, arr.length - 1);
}

function qs(arr, start, end){
  if(start < end){
    var k = partition2(arr, start, end);
    qs(arr, start, k);
    qs(arr, k + 1, end);
  }
}

// Lomuto Partition
function partition(arr, start, end){
  var pivot = arr[end];
  var i = start - 1;
  for (var j = start; j < end; j++) {
    if(arr[j] <= pivot){
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, end);
  return i + 1;
}

// Hoare Partition
function partition2(arr, start, end){
  var pivot = arr[start];
  var i = start - 1;
  var j = end + 1;
  while(true){
    do{
      i++;
    }while(arr[i] < pivot);
    do{
      j--;
    }while(arr[j] > pivot);
    if(i >= j){
      return j;
    }
    swap(arr, i ,j);
  }
}

function swap(arr, i, j){
  var t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
}

var array = [3,7,2,1,6,4,5];
quicksort(array);
console.log("result:  ", array);

// 实现归并排序

function mergesort(arr){
  ms(arr, 0, arr.length - 1);
}

function ms(arr, start, end){
  if(start < end){
    var mid = Math.floor((start + end) / 2);
    ms(arr, start, mid);
    ms(arr, mid + 1, end);
    merge(arr, start, mid, end);
  }
}

function merge(arr, start, mid, end){
  var t = [];
  var i = start;
  var j = mid + 1;
  while(i <= mid && j <= end){
    if(arr[i] <= arr[j]){
      t.push(arr[i]);
      i++;
    }else{
      t.push(arr[j]);
      j++;
    }
  }
  while(i <= mid){
    t.push(arr[i]);
    i++;
  }
  while(j <= end){
    t.push(arr[j]);
    j++;
  }
  for (var k = start; k <= end; k++) {
    arr[k] = t[k - start];
  }
}

var arr = [6,3,2,1,5,4,7,0,9,2,11,15,256,-1];
mergesort(arr);
console.log(arr);