การ Implement Merge Sort ใน JavaScript

Merge Sort - Divide and Conquer

Merge Sort เป็น O(n log n) Stable Sort แบ่ง Array ครึ่งๆ จนเหลือ 1 Element แล้ว Merge กลับมาจากน้อยไปมาก

ขั้นตอน

1. Divide: แบ่ง Array เป็น 2 ส่วน ซ้ำจนเหลือ 1 Element
2. Conquer: Merge 2 Sorted Arrays กลับมาเป็น 1 Sorted Array
3. Combine: ทำซ้ำจนได้ Array เดียวเรียงครบ

Implementation

<script>
  function mergeSort(array) {
    // Base Case
    if (array.length <= 1) return array;
    
    // Divide
    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid);
    const right = array.slice(mid);
    
    // Conquer + Combine
    return merge(mergeSort(left), mergeSort(right));
  }
  
  function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        result.push(left[i++]);
      } else {
        result.push(right[j++]);
      }
    }
    
    // เหลือด้านไหนก็ Push ทั้งหมด
    return result.concat(left.slice(i)).concat(right.slice(j));
  }
  
  const list = [4, 7, 5, 9, 1, 3, 8, 2];
  console.log(mergeSort(list)); // [1, 2, 3, 4, 5, 7, 8, 9]
</script>

Complexity

특징

• Stable: รักษาลำดับเดิมของค่าเท่ากัน
• Not In-place: ต้องการ O(n) Extra Space
• Predictable: เวลาคงที่ O(n log n) ทุก Case
• เหมาะกับ Linked List (Merge แบบ In-place ได้)