Merge Sort เทียบ Quick Sort ใน JavaScript

Merge Sort เป็นเทคนิคการเรียงลำดับแบบ Divide and Conquer มี Worst-case Time Complexity เป็น O(n log n) แต่ต้องใช้พื้นที่เพิ่ม O(n) Memory

Implementation: สร้าง 2 Functions คือ mergeSort และ merge

merge - รับ 2 Arguments คือ 2 Partial Arrays รวมกันเป็น Array เดียวโดย Insert Elements เรียงลำดับ

mergeSort - เรียก mergeSort ซ้ำกับ Left และ Right Halves แล้วใช้ merge รวมส่วนๆ กลับกัน

Merge Function

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

MergeSort Inner Function

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)); }

Complete Code with Test

function mergeSort(arr, compare = (a, b) => a < b) {    function merge(left, right) { ... }    function mergeSortInner(arr) { ... }    return mergeSortInner(arr); }

Quick Sort

Quick Sort เป็น Sorting Algorithm ที่มีประสิทธิภาพสูง 基于 Partitioning Array เป็น Smaller Arrays เลือก Pivot แบ่ง Array เป็น 2 ส่วน: น้อยกว่า Pivot และมากกว่า Pivot เรียก Recursive สองครั้งสำหรับ Subarrays Average และ Worst Case Complexity เป็น O(n²)

Partition Process

เลือก Element แรกเป็น Pivot (Random ใน Randomized Quick Sort) เปรียบเทียบ Element ที่เหลือกับ Pivot ย้าย Elements น้อยกว่า Pivot ไปซ้าย มากกว่าไปขวา จน Pivot อยู่ตำแหน่งที่ถูกต้อง

Partition Function

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 += 1;       }    }    swap(arr, pivotIndex - 1, low);    return pivotIndex - 1; } function swap(arr, i, j) {    let temp = arr[i];    arr[i] = arr[j];    arr[j] = temp; }

QuickSort Function

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);    } }