Advanced Sorting

Merge Sort คืออะไร

Merge Sort คืออัลกอริทึมเรียงข้อมูลแบบเปรียบเทียบ (comparison-based sorting) ที่ใช้แนวคิด "แบ่งให้เล็กก่อน แล้วค่อยรวมกลับ" — แบ่งอาเรย์ออกเป็นครึ่งซ้ายและครึ่งขวาแบบ recursion จนเหลือสมาชิกเดี่ยว จากนั้นค่อย merge กลับขึ้นมาเป็นอาเรย์ที่เรียงสมบูรณ์

เอกลักษณ์ที่โดดเด่น: Merge Sort มี Time Complexity เท่ากันทุกรณี — Best, Average, Worst เป็น O(n log n) ไม่มี worst case ที่ตกเป็น O(n²) แบบ Quick Sort หรืออัลกอริทึมที่พึ่งพา pivot

• ใช้ Divide and Conquer — แบ่งอาเรย์ย่อยจนเหลือ 1 ตัว แล้ว merge กลับ
• Time Complexity คงที่ O(n log n) ทุกกรณี — คาดเดาเวลาได้แม่นยำ
• เป็น stable sort — ค่าที่เท่ากันรักษาลำดับเดิมไว้ได้

แนวคิด Divide and Conquer

Divide and Conquer แปลว่า "แบ่งปัญหาแล้วพิชิตทีละส่วน" — เป็นแม่แบบการแก้ปัญหาที่แบ่งปัญหาใหญ่ให้เป็นปัญหาย่อยที่แก้ได้ง่ายกว่า แล้วรวมคำตอบย่อยกลับมาเป็นคำตอบของปัญหาเดิม ประกอบด้วย 3 ขั้นตอนหลัก

• Divide — แบ่งอาเรย์ออกเป็นครึ่งซ้ายและครึ่งขวา (split ที่ index กลาง)
• Conquer — เรียก mergeSort ซ้ำกับครึ่งซ้ายและครึ่งขวาจนเหลือสมาชิกเดี่ยว ซึ่งถือว่าเรียงแล้วโดยธรรมชาติ
• Combine — merge อาเรย์ย่อยทั้งสองฝั่งที่เรียงแล้ว ให้กลายเป็นอาเรย์เดียวที่เรียงสมบูรณ์

การแบ่งครึ่งจนเหลือสมาชิกเดี่ยว

Merge Sort เริ่มด้วยการแบ่งอาเรย์ออกเป็นสองส่วนที่ index กลาง (mid = floor(length / 2)) — เรียกซ้ำกับฝั่งซ้าย `[0..mid-1]` และฝั่งขวา `[mid..length-1]` ต่อไปเรื่อย ๆ จนแต่ละชิ้นมีสมาชิก 0 หรือ 1 ตัว ซึ่งเป็น base case ที่ถือว่าเรียงแล้ว

ตัวอย่าง: จาก `[38, 27, 43, 3, 9, 82, 10]` → แบ่งเป็น `[38, 27, 43]` และ `[3, 9, 82, 10]` → แบ่งต่อเป็น `[38]`, `[27, 43]`, `[3, 9]`, `[82, 10]` → แบ่งจนสุดเป็น `[38]`, `[27]`, `[43]`, `[3]`, `[9]`, `[82]`, `[10]` — ทุกก้อนคือ singleton ที่เรียงแล้ว

แผนภาพต้นไม้แสดงการแบ่งอาเรย์ทีละครึ่ง

ผลลัพธ์สุดท้ายของการแบ่ง — ทุกชิ้นเป็น singleton

การรวมกลับด้วยการ merge

เมื่อแบ่งจนสุดแล้ว จะเริ่มรวมจากชั้นล่างสุดกลับขึ้นไปทีละชั้น — ใช้ฟังก์ชัน `merge(left, right)` เพื่อรวมอาเรย์ย่อย 2 ชุดที่เรียงอยู่แล้วให้เป็นอาเรย์เดียวที่เรียงถูกต้อง

ตัวอย่างจากล่างขึ้นบน: `[27] + [43] → [27, 43]`, `[3] + [9] → [3, 9]`, `[82] + [10] → [10, 82]` → ชั้นต่อไป: `[38] + [27, 43] → [27, 38, 43]`, `[3, 9] + [10, 82] → [3, 9, 10, 82]` → ชั้นสุดท้าย: `[27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]`

การ merge แต่ละครั้งใช้เทคนิค "สองพอยน์เตอร์" — ตัวชี้ i ชี้ที่ left[0], ตัวชี้ j ชี้ที่ right[0] — เทียบค่าที่หัวแถวทั้งสองฝั่ง แล้วหยิบค่าที่น้อยกว่าใส่ result โดยเลื่อนพอยน์เตอร์ของฝั่งที่ถูกหยิบไปทีละ 1 ตำแหน่ง

แผนภาพการรวมกลับทีละชั้น — จาก singleton สู่อาเรย์สมบูรณ์

การเทียบ head element ของ left และ right — หยิบตัวน้อยกว่าก่อน

โค้ด Merge Sort

ฟังก์ชัน mergeSort(values):
  ถ้า values.length <= 1:
    คืนค่า values

  mid = floor(values.length / 2)
  left = values ช่วง [0..mid-1]
  right = values ช่วง [mid..ท้าย]

  leftSorted = mergeSort(left)
  rightSorted = mergeSort(right)

  คืนค่า merge(leftSorted, rightSorted)

ฟังก์ชัน merge(left, right):
  result = []
  i = 0
  j = 0

  ขณะที่ i < left.length และ j < right.length:
    ถ้า left[i] <= right[j]:
      เพิ่ม left[i] ลง result
      i = i + 1
    ไม่เช่นนั้น:
      เพิ่ม right[j] ลง result
      j = j + 1

  ต่อท้าย result ด้วยสมาชิกที่เหลือใน left
  ต่อท้าย result ด้วยสมาชิกที่เหลือใน right

  คืนค่า result

function merge(left, right) {
  const merged = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.push(left[i]);
      i += 1;
    } else {
      merged.push(right[j]);
      j += 1;
    }
  }

  while (i < left.length) {
    merged.push(left[i]);
    i += 1;
  }

  while (j < right.length) {
    merged.push(right[j]);
    j += 1;
  }

  return merged;
}

function mergeSort(values) {
  if (values.length <= 1) {
    return values;
  }

  const mid = Math.floor(values.length / 2);
  const left = values.slice(0, mid);
  const right = values.slice(mid);

  const leftSorted = mergeSort(left);
  const rightSorted = mergeSort(right);

  return merge(leftSorted, rightSorted);
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

ข้อควรสังเกต: `mergeSort` ใช้ `values.slice()` สร้างอาเรย์ใหม่ (ไม่แก้ไขต้นฉบับ) — ทำให้ Merge Sort เป็น out-of-place algorithm ส่วน `merge` ทำงานกับสองอาเรย์ที่เรียงแล้วและสร้าง merged array ใหม่ ซึ่งเป็นสาเหตุหลักที่ Merge Sort ใช้ memory เพิ่ม O(n)

Time & Space Complexity

Space Complexity: Merge Sort แบบมาตรฐานใช้อาเรย์เสริมระหว่าง merge จึงใช้พื้นที่เพิ่ม O(n) — รวมกับ call stack ของ recursion (log n ชั้น) แต่ส่วนใหญ่คิดที่ O(n) เพราะอาเรย์เสริมใช้พื้นที่มากกว่า call stack มาก

ข้อดี ข้อเสีย และกรณีใช้งาน

• เวลา O(n log n) คงเส้นคงวาทุกกรณี — ไม่มี worst case แบบ Quick Sort
• เป็น stable sort — ค่าที่เท่ากันจะรักษาลำดับเดิมไว้ (มีประโยชน์เมื่อเรียงหลายคีย์ต่อเนื่อง)
• เหมาะกับ linked list — ไม่ต้อง random access แบบ Quick Sort และ merge บน linked list ทำได้ O(1) space

• ใช้หน่วยความจำเสริม O(n) — เพราะต้องสร้างอาเรย์ใหม่ในระหว่าง merge
• โค้ดซับซ้อนกว่า Insertion/Selection Sort สำหรับผู้เริ่มต้น
• ถ้าข้อมูลเล็กมาก (< 50 ตัว) ค่า overhead ของ recursion และ slice อาจไม่คุ้ม

เหมาะกับ: งานที่ต้องเรียงข้อมูลปริมาณมากและต้องการเวลาที่คาดเดาได้, งานเรียง linked list, งานที่ต้องการ stable sort (เช่นเรียงไฟล์ตามวันที่แล้วเรียงตามขนาด), และ external sorting (เรียงข้อมูลที่ใหญ่กว่า RAM)

ทบทวนความเข้าใจ

แบบฝึกหัดที่ 1: mergeSortedArrays — รวม 2 อาเรย์ที่เรียงแล้ว

เริ่มจากแกนกลางของ Merge Sort — ฟังก์ชัน merge ที่รับอาเรย์ 2 ชุดที่เรียงแล้ว (left, right) แล้วคืนอาเรย์ใหม่ที่รวมกันและเรียงสมบูรณ์

แบบฝึกหัดที่ 2: mergeSort — เรียงจากน้อยไปมาก

นำฟังก์ชัน merge มาใช้ร่วมกับ recursion — แบ่งอาเรย์ครึ่งซ้าย/ขวา เรียก mergeSort ซ้ำกับทั้งสองฝั่ง แล้ว merge กลับ

แบบฝึกหัดที่ 3: mergeSortDescending — เรียงจากมากไปน้อย

ทดสอบความเข้าใจ — เปลี่ยนการ merge จาก ascending เป็น descending โดยใช้โครงสร้างเดิมทุกอย่าง แค่กลับเงื่อนไขตอนเทียบหัวแถว