So sánh Merge Sort vs Quick Sort trong JavaScript

Merge Sort

Kỹ thuật sắp xếp dựa trên chia để trị (divide and conquer). Time complexity worst-case: O(n log n). Tốn O(n) memory thêm.

merge: Gộp 2 mảng đã sort thành 1 mảng sort.

mergeSort: Đệ quy chia mảng, sort từng nửa, merge lại.

Triển khai Merge Sort

function merge(left, right) {
  let mergedArr = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) mergedArr.push(left[i++]);
    else mergedArr.push(right[j++]);
  }
  return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr, compare = (a, b) => a < b) {
  function mergeSortInner(arr) {
    if (arr.length < 2) return arr;
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSortInner(left), mergeSortInner(right));
  }
  return mergeSortInner(arr);
}

Test

let arr = [5, 8, 9, 12, -8, 31, 2];
arr = mergeSort(arr); console.log(arr); // [-8, 2, 5, 8, 9, 12, 31]
arr = mergeSort(arr, (a, b) => a > b); console.log(arr); // [31, 12, 9, 8, 5, 2, -8]

// Sort object
arr = [{name:'Harry',age:20},{name:'Jacob',age:25},{name:'Mary',age:12}];
arr = mergeSort(arr, (a,b) => a.name < b.name); // Sort by name
arr = mergeSort(arr, (a,b) => a.age > b.age);  // Sort by age desc

Quick Sort

Hiệu quả cao, dựa trên partition. Chia mảng thành 2: nhỏ hơn pivot và lớn hơn pivot. Đệ quy sort 2 mảng con. Average O(n log n), worst O(n²).

Partition

function partition(arr, low, high, compare) {
  let pivotIndex = low + 1;
  for (let i = pivotIndex; i < high; i++) {
    if (compare(arr[i], arr[low])) {
      swap(arr, i, pivotIndex);
      pivotIndex++;
    }
  }
  swap(arr, pivotIndex - 1, low);
  return pivotIndex - 1;
}
function swap(arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]]; }

Quick Sort

function QuickSort(arr, low, high, compare = (l, r) => l < r) {
  if (high - low > 0) {
    let mid = partition(arr, low, high, compare);
    QuickSort(arr, low, mid, compare);
    QuickSort(arr, mid + 1, high, compare);
  }
}

Test

let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr); // [-6, 1, 2, 3, 5, 8, 9, 10, 45]

So sánh: