การค้นหาและการเรียงลำดับบทที่ 20Merge Sort

Merge Sort แบบละเอียด เข้าใจง่าย ตั้งแต่พื้นฐานถึงใช้งานจริง

บทนี้จะพาคุณเข้าใจ Merge Sort แบบเห็นภาพครบทั้งการแบ่งปัญหา (Divide and Conquer), การทำงานของ recursion และขั้นตอน merge ที่เป็นหัวใจสำคัญของอัลกอริทึมนี้

1. Merge Sort คืออะไร

Merge Sort คืออัลกอริทึมเรียงข้อมูลแบบเปรียบเทียบ (comparison-based sorting) ที่ใช้แนวคิด “แบ่งให้เล็กก่อน แล้วค่อยรวมกลับ” เพื่อให้เรียงข้อมูลได้อย่างมีประสิทธิภาพ

จุดเด่นคือเวลาในการทำงานมีความเสถียร: Best, Average, Worst เป็น O(n log n) เหมือนกันทั้งหมด

2. แนวคิด Divide and Conquer คืออะไร

Divide and Conquer แปลตรงตัวว่า “แบ่งปัญหาแล้วพิชิตทีละส่วน” โดยมี 3 ขั้น: (1) Divide: แบ่งปัญหาใหญ่เป็นปัญหาเล็ก, (2) Conquer: แก้ปัญหาเล็กให้เสร็จ, (3) Combine: รวมคำตอบย่อยกลับเป็นคำตอบใหญ่

สำหรับ Merge Sort เราแบ่ง array ออกเป็นครึ่งซ้าย/ขวาจนเหลือสมาชิกเดี่ยว แล้วค่อย merge กลับขึ้นมาเป็นลำดับที่ถูกต้อง

3. ภาพรวมการทำงาน: แบ่ง -> เรียง -> รวม

ขั้นแรก “แบ่ง”: ตัด array เป็น 2 ครึ่งซ้ำ ๆ จนเหลือสมาชิกเดี่ยว ซึ่งถือว่าเรียงแล้วโดยธรรมชาติ

ขั้นสอง “เรียง”: เกิดระหว่างการ merge เพราะเราจะเปรียบเทียบค่าหัวแถวของฝั่งซ้ายและขวา แล้วหยิบค่าที่น้อยกว่าใส่ผลลัพธ์

ขั้นสาม “รวม”: ทำซ้ำจากชั้นล่างสุดขึ้นชั้นบนสุด จนได้ array ที่เรียงครบทั้งชุด

4. อธิบาย recursion แบบไม่ซับซ้อน

Recursion คือฟังก์ชันที่ “เรียกตัวเอง” เพื่อแก้ปัญหาแบบเดียวกันในเวอร์ชันที่เล็กลง ถ้าจะจำแบบง่าย ๆ ให้คิดว่า “งานเดิม แต่ชิ้นเล็กลงเรื่อย ๆ”

ใน Merge Sort เงื่อนไขหยุด (base case) คือเมื่อ array มี 0 หรือ 1 สมาชิก เพราะไม่ต้องเรียงเพิ่มแล้ว จากนั้นค่อยย้อนกลับมารวมผลทีละชั้น

ทำไมต้องแบ่งครึ่ง ๆ: เพราะความลึกของการแบ่งจะเหลือประมาณ log n ชั้น ทำให้จำนวนรอบการรวมมีประสิทธิภาพ และแต่ละชั้นรวมข้อมูลรวมกันเพียง n ตัว

5. ตัวอย่าง array เช่น [38, 27, 43, 3, 9, 82, 10]

เราจะใช้ตัวอย่างนี้ตลอดบท:[38, 27, 43, 3, 9, 82, 10]

เป้าหมายคือเรียงจากน้อยไปมาก โดยอธิบายทุกชั้นทั้งตอนแตกและตอนรวม

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

เราแบ่งครึ่งซ้ำ ๆ ดังนี้: [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]

แผนภาพต้นไม้แสดงการแบ่ง array ของ Merge Sort ออกเป็นครึ่งซ้ายและขวา

แผนภาพแสดงผลการแตกจนเหลือสมาชิกเดี่ยวใน Merge Sort

7. แสดงขั้นตอนการ merge กลับขึ้นมาอย่างละเอียด

เมื่อแตกสุดแล้วจะเริ่มรวมจากล่างขึ้นบน: [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 Sort จากอาเรย์ย่อยจนเป็นอาเรย์หลัก

8. อธิบายการเปรียบเทียบระหว่าง left array และ right array

สมมติ left = [27, 38, 43] และ right = [3, 9, 10, 82] เราจะดูค่าหน้าแถวเท่านั้นในแต่ละรอบ:

เทียบ 27 กับ 3 -> เอา 3, เทียบ 27 กับ 9 -> เอา 9, เทียบ 27 กับ 10 -> เอา 10, เทียบ 27 กับ 82 -> เอา 27, ต่อด้วย 38, 43 และ 82

หลักจำง่าย: “เทียบหัวแถวสองฝั่ง แล้วหยิบตัวที่น้อยกว่า” ทำซ้ำจนฝั่งใดฝั่งหนึ่งหมด จากนั้นเอาฝั่งที่เหลือต่อท้ายได้เลย

ภาพไฮไลต์การเทียบค่าระหว่างฝั่งซ้ายและขวาระหว่างขั้น merge ใน Merge Sort

9. Pseudocode

Pseudocode: Merge Sortbash

โครงคิดก่อนแปลงเป็นโค้ดจริง

ฟังก์ชัน 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

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: Merge SortJS

ใช้ฟังก์ชัน merge แยกจาก mergeSort เพื่ออ่านง่ายและทดสอบง่าย

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

  // เทียบหัวแถวของ left และ right แล้วหยิบตัวที่น้อยกว่า
  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]

โค้ดถูกแยกเป็น 2 ส่วนชัดเจน: `mergeSort` ดูแลการแบ่งและเรียกซ้ำ, ส่วน `merge` ดูแลการรวมอาเรย์ย่อยที่เรียงแล้วให้เป็นอาเรย์ใหม่ที่เรียงถูกต้อง

11. Best / Average / Worst Time Complexity

Best: O(n log n)

ถึงข้อมูลจะเกือบเรียงอยู่แล้ว ก็ยังต้องแบ่งและ merge ตามโครงสร้างเดิม

Average: O(n log n)

มี log n ชั้นของการแบ่ง และแต่ละชั้นประมวลผลรวม n สมาชิก

Worst: O(n log n)

กรณีแย่ที่สุดยังอยู่ที่ระดับเดียวกัน เพราะขั้น merge ทำงานเป็นระบบทุกชั้น

12. Space Complexity

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

13. ข้อดี

เวลาในการทำงานสม่ำเสมอ O(n log n) ทุกกรณี

เป็นอัลกอริทึมแบบ stable (ในเวอร์ชัน merge ที่รักษาลำดับค่าซ้ำ)

เหมาะกับข้อมูลขนาดใหญ่และงานที่ต้องการความคาดเดาได้ของเวลา

14. ข้อเสีย

ใช้หน่วยความจำเพิ่ม O(n) เพราะต้องมีพื้นที่ช่วยตอน merge

โค้ดซับซ้อนกว่า Insertion/Selection สำหรับผู้เริ่มต้น

กับข้อมูลขนาดเล็กมาก ๆ ค่า overhead ของ recursion อาจไม่คุ้ม

15. เหมาะกับกรณีไหน

เหมาะกับงานที่ต้องเรียงข้อมูลปริมาณมาก, ต้องการเวลา O(n log n) ที่คาดเดาได้ และงานที่ต้องการ stable sort เช่นเรียงหลายคีย์ต่อเนื่องกัน

16. เปรียบเทียบสั้น ๆ กับ Quick Sort

Merge Sort

เวลาคงเส้นคงวา O(n log n) แต่แลกด้วยพื้นที่เสริม O(n)

Quick Sort

เฉลี่ยเร็วมากและมักใช้หน่วยความจำน้อยกว่า แต่กรณีแย่อาจตกเป็น O(n²) หากเลือก pivot ไม่เหมาะสม

17. สรุปท้ายบท

Merge Sort คือการใช้ Divide and Conquer แบ่งปัญหาให้เล็กลงจนแก้ง่าย แล้วรวมกลับด้วยขั้น merge ที่เปรียบเทียบหัวแถวซ้าย/ขวาทีละก้าว

ถ้าคุณเข้าใจ “แบ่งครึ่งจนเดี่ยว” และ “รวมกลับทีละชั้น” ได้ชัด คุณจะต่อยอดไปอัลกอริทึมสาย recursion อื่นได้ง่ายขึ้นมาก

18. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย

ข้อ 1: เขียนฟังก์ชัน mergeSortedArrays(left, right)

แนวเฉลยย่อ: ใช้ตัวชี้ i, j เทียบหัวแถวสองฝั่ง แล้ว push ตัวที่น้อยกว่าไปเรื่อย ๆ จากนั้นต่อท้ายฝั่งที่เหลือ

ข้อ 2: เขียนฟังก์ชัน mergeSort(values) แบบ recursion

แนวเฉลยย่อ: base case คือความยาว <= 1, แบ่งครึ่งด้วย mid, เรียก mergeSort ซ้าย/ขวา แล้ว merge กลับ

ข้อ 3: เขียน mergeSortDescending(values) ให้เรียงจากมากไปน้อย

แนวเฉลยย่อ: โครงสร้างเหมือนเดิมทุกอย่าง แค่กลับเงื่อนไขในขั้น merge ให้หยิบค่าที่มากกว่าก่อน

ฝึกลงมือจริงใน playground ต่อได้ที่ Merge Sort Lab ซึ่งมี runtime checks ให้ตรวจผลลัพธ์ทันทีทั้ง 3 โจทย์

ไปทำ Merge Sort Lab

การค้นหาและการเรียงลำดับบทที่ 20Merge Sort

Merge Sort แบบละเอียด เข้าใจง่าย ตั้งแต่พื้นฐานถึงใช้งานจริง

1. Merge Sort คืออะไร

2. แนวคิด Divide and Conquer คืออะไร

3. ภาพรวมการทำงาน: แบ่ง -> เรียง -> รวม

4. อธิบาย recursion แบบไม่ซับซ้อน

5. ตัวอย่าง array เช่น [38, 27, 43, 3, 9, 82, 10]

เราจะใช้ตัวอย่างนี้ตลอดบท:[38, 27, 43, 3, 9, 82, 10]

เป้าหมายคือเรียงจากน้อยไปมาก โดยอธิบายทุกชั้นทั้งตอนแตกและตอนรวม

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

7. แสดงขั้นตอนการ merge กลับขึ้นมาอย่างละเอียด

เมื่อแตกสุดแล้วจะเริ่มรวมจากล่างขึ้นบน: [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]

8. อธิบายการเปรียบเทียบระหว่าง left array และ right array

สมมติ left = [27, 38, 43] และ right = [3, 9, 10, 82] เราจะดูค่าหน้าแถวเท่านั้นในแต่ละรอบ:

9. Pseudocode

Pseudocode: Merge Sortbash

โครงคิดก่อนแปลงเป็นโค้ดจริง

ฟังก์ชัน 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

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: Merge SortJS

ใช้ฟังก์ชัน merge แยกจาก mergeSort เพื่ออ่านง่ายและทดสอบง่าย

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

  // เทียบหัวแถวของ left และ right แล้วหยิบตัวที่น้อยกว่า
  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]

11. Best / Average / Worst Time Complexity

Best: O(n log n)

ถึงข้อมูลจะเกือบเรียงอยู่แล้ว ก็ยังต้องแบ่งและ merge ตามโครงสร้างเดิม

Average: O(n log n)

มี log n ชั้นของการแบ่ง และแต่ละชั้นประมวลผลรวม n สมาชิก

Worst: O(n log n)

12. Space Complexity

13. ข้อดี

เวลาในการทำงานสม่ำเสมอ O(n log n) ทุกกรณี

เป็นอัลกอริทึมแบบ stable (ในเวอร์ชัน merge ที่รักษาลำดับค่าซ้ำ)

เหมาะกับข้อมูลขนาดใหญ่และงานที่ต้องการความคาดเดาได้ของเวลา

14. ข้อเสีย

ใช้หน่วยความจำเพิ่ม O(n) เพราะต้องมีพื้นที่ช่วยตอน merge

โค้ดซับซ้อนกว่า Insertion/Selection สำหรับผู้เริ่มต้น

กับข้อมูลขนาดเล็กมาก ๆ ค่า overhead ของ recursion อาจไม่คุ้ม

15. เหมาะกับกรณีไหน

16. เปรียบเทียบสั้น ๆ กับ Quick Sort

Merge Sort

เวลาคงเส้นคงวา O(n log n) แต่แลกด้วยพื้นที่เสริม O(n)

Quick Sort

17. สรุปท้ายบท

18. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย

ข้อ 1: เขียนฟังก์ชัน mergeSortedArrays(left, right)

ข้อ 2: เขียนฟังก์ชัน mergeSort(values) แบบ recursion

ข้อ 3: เขียน mergeSortDescending(values) ให้เรียงจากมากไปน้อย

ไปทำ Merge Sort Lab

Data Structures & Algorithms

1. Merge Sort คืออะไร

2. แนวคิด Divide and Conquer คืออะไร

3. ภาพรวมการทำงาน: แบ่ง -> เรียง -> รวม

4. อธิบาย recursion แบบไม่ซับซ้อน

5. ตัวอย่าง array เช่น [38, 27, 43, 3, 9, 82, 10]

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

7. แสดงขั้นตอนการ merge กลับขึ้นมาอย่างละเอียด

8. อธิบายการเปรียบเทียบระหว่าง left array และ right array

9. Pseudocode

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

11. Best / Average / Worst Time Complexity

12. Space Complexity

13. ข้อดี

14. ข้อเสีย

15. เหมาะกับกรณีไหน

16. เปรียบเทียบสั้น ๆ กับ Quick Sort

17. สรุปท้ายบท

18. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย

Loading

Data Structures & Algorithms

1. Merge Sort คืออะไร

2. แนวคิด Divide and Conquer คืออะไร

3. ภาพรวมการทำงาน: แบ่ง -> เรียง -> รวม

4. อธิบาย recursion แบบไม่ซับซ้อน

5. ตัวอย่าง array เช่น [38, 27, 43, 3, 9, 82, 10]

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

7. แสดงขั้นตอนการ merge กลับขึ้นมาอย่างละเอียด

8. อธิบายการเปรียบเทียบระหว่าง left array และ right array

9. Pseudocode

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

11. Best / Average / Worst Time Complexity

12. Space Complexity

13. ข้อดี

14. ข้อเสีย

15. เหมาะกับกรณีไหน

16. เปรียบเทียบสั้น ๆ กับ Quick Sort

17. สรุปท้ายบท

18. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย