LeetCode #88 Merge Sorted Array: ช้าง กระต่าย นกฮูก ประลองรวมคิว

LeetCode #88 Merge Sorted Array ให้เราเอาข้อมูลสองชุดที่เรียงจากน้อยไปมากอยู่แล้วมารวมกัน โดย nums1 มีช่องทั้งหมด m+n ช่อง แต่ข้อมูลจริงอยู่แค่ m ช่องแรก ส่วนศูนย์ท้ายแถวเป็นที่ว่างสำหรับข้อมูล n ตัวจาก nums2 ครับ ผลลัพธ์ต้องเรียงอยู่ใน nums1 ตัวเดิม ไม่ใช่คืนลิสต์ใหม่ออกมาแทน

งานนี้เหมือนรวมคิวลูกค้าสองสาขาที่เรียงตามเวลาอยู่แล้ว ให้กลายเป็นคิวเดียวที่ยังเรียงเวลาถูกต้อง

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
→ nums1 = [1, 2, 2, 3, 5, 6]

วันนี้ช้างเทกอง กระต่ายจองโต๊ะใหม่ และนกฮูกเดินถอยหลัง จะมาประลองกัน โดยมี บารอน สิงโตทะเลสวมเสื้อโค้ตเป็นกรรมการ

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
ช้างเทกอง ชื่อเล่น “พี่เท”	ใส่ข้อมูลท้ายแถวแล้ว sort	ใจใหญ่ ชอบยกงานหนักให้เครื่องมือสำเร็จรูป
กระต่ายจองโต๊ะใหม่ ชื่อเล่น “น้องโต๊ะ”	สองตัวชี้เดินหน้า สร้างลิสต์ใหม่แล้วคัดลอกกลับ	เป็นระเบียบ ขอพื้นที่วางของก่อนลงมือเสมอ
นกฮูกเดินถอยหลัง ชื่อเล่น “ฮูกถอย”	สามตัวชี้ เติมจากท้ายแถว	รอบคอบ มองทางหนีก่อนขยับของ
บารอน สิงโตทะเลในเสื้อโค้ต	กรรมการ	ดูทั้งหลักฐานเวลาและกติกาเรื่องพื้นที่

ก่อนเปิดสนาม ผมขอแยกคำสองคำครับ การแก้ nums1 ตัวเดิมคือเงื่อนไขด้านผลลัพธ์ ส่วน in-place ในแง่อัลกอริทึมมักหมายถึงทำในพื้นที่เดิมโดยใช้ที่เก็บเพิ่มเพียงคงที่ สองวิธีแรกแก้ลิสต์เดิมได้ แต่ยังต้องใช้พื้นที่ช่วยที่โตตามข้อมูล

ต่อไปให้ k = m+n เป็นจำนวนข้อมูลรวม เวลา O(k) หมายถึงเมื่อข้อมูลโต งานก็โตตามสัดส่วน ส่วน O(1) หมายถึงใช้ทรัพยากรเพิ่มคงที่ ไม่ได้หมายความว่าใช้เวลาเพียงครั้งเดียวทุกกรณีครับ

วิธีที่ 1: ช้างเทกอง — ใส่ท้ายแล้ว sort

พี่เทชูงวงขึ้นแล้วบอกว่า “ท้ายแถวยังว่าง เทของลงไปก่อน เดี๋ยวจัดทีเดียว!” วิธีนี้เขียนได้แค่ nums1[m:] = nums2 แล้วตามด้วย nums1.sort() ก็จบ

การกำหนดช่วงด้วย slice คือแทนค่าตั้งแต่ตำแหน่ง m ถึงท้ายลิสต์ พอดีกับช่องสำรอง n ช่องตามกติกา เราไม่ได้เอาศูนย์สำรองไปเป็นข้อมูลจริง เพราะช่วงนั้นถูกแทนทั้งหมดก่อนเรียง ส่วนศูนย์ที่อยู่ใน m ช่องแรกยังเป็นข้อมูลจริงและต้องเก็บไว้

คู่มือการเรียงของ Python อธิบายว่า list.sort() แก้ลิสต์เดิม และ Timsort ใช้ประโยชน์จากลำดับที่มีอยู่แล้วได้ กรณีนี้แต่ละชุดเรียงมาอยู่ก่อน จึงมีโครงสร้างให้ตัวเรียงใช้ประโยชน์ แต่ผมยังระบุขอบเขตทั่วไปแบบอนุรักษ์นิยม ไม่สัญญาว่าทุกอินพุตจะมีต้นทุนเท่ากัน

เวลา: ขอบเขตทั่วไป O(k log k) โดย log k เป็นตัวคูณที่โตช้ากว่าจำนวนข้อมูลมาก ข้อมูลที่มีช่วงเรียงอยู่แล้วอาจทำได้ดีกว่าขอบเขตนี้
หน่วยความจำเพิ่ม: เผื่อ O(k) สำหรับพื้นที่ช่วยของการเรียง อย่าเห็นคำว่าแก้ลิสต์เดิมแล้วสรุปว่าใช้ที่เพิ่มคงที่
ข้อดี: สั้น อ่านง่าย ใช้งานตัวเรียงที่ทำงานส่วนหลักในระดับ C แทนการวนเปรียบเทียบเองด้วย Python
ข้อเสีย/edge cases: ไม่แสดงทักษะการรวมข้อมูลแบบเชิงเส้น และไม่รับประกันพื้นที่เพิ่ม O(1); เมื่อ m=0 จะใส่ nums2 ทั้งชุด เมื่อ n=0 ก็ยังเรียกเรียงข้อมูลเดิมอีกครั้ง

น้องโต๊ะกระดิกหู “งานรวมของที่เรียงแล้ว ทำไมต้องเรียงใหม่ล่ะพี่?” พี่เทยิ้ม “โค้ดสั้นไว้ก่อน แต่เดี๋ยวดูนาฬิกากันด้วยนะ” คำท้านี้สำคัญครับ เพราะจำนวนขั้นตอนเชิงทฤษฎีกับเวลาจริงของ Python ไม่จำเป็นต้องจัดอันดับเหมือนกัน

วิธีที่ 2: กระต่ายจองโต๊ะใหม่ — สองตัวชี้เดินหน้า

น้องโต๊ะปูผ้าบนโต๊ะข้าง ๆ แล้วหยิบหัวคิวที่น้อยกว่ามาวางทีละตัว ตัวชี้หรือ pointer ในที่นี้คือเลขตำแหน่งในลิสต์ ไม่ใช่การจัดการที่อยู่หน่วยความจำเอง เรามี i ดูข้อมูลจริงของ nums1 และ j ดู nums2 ครับ

เมื่อเลือกฝั่งไหน ก็เลื่อนตำแหน่งฝั่งนั้นไปหนึ่งช่อง พอฝั่งหนึ่งหมด ให้ย้ายที่เหลือของอีกฝั่งมาต่อได้เลย เพราะมันเรียงอยู่แล้ว สุดท้ายใช้ nums1[:] = merged คัดลอกคำตอบกลับเข้าไปในลิสต์เดิม

แถวแรก:  [1, 3]     i เริ่มที่ 1
แถวสอง:  [2, 4]     j เริ่มที่ 2
โต๊ะใหม่: [] → [1] → [1, 2] → [1, 2, 3] → [1, 2, 3, 4]
คัดลอกโต๊ะใหม่กลับลง nums1

หัวใจคือทุกครั้งที่หยิบ เราได้ค่าน้อยที่สุดของข้อมูลที่ยังเหลืออยู่ จึงต่อท้ายคำตอบได้อย่างมั่นใจ ลูปสุดท้ายสองชุดในโค้ดใช้เก็บเศษจากแต่ละฝั่ง และกำหนดขอบเขตด้วย m กับ n ชัดเจน ไม่เดินเข้าไปอ่านศูนย์สำรอง

เวลา: O(k) แต่ละข้อมูลถูกอ่านและเติมลงคำตอบหนึ่งครั้ง แล้วมีการคัดลอกกลับอีกหนึ่งรอบ ซึ่งยังโตตามจำนวนข้อมูล
หน่วยความจำเพิ่ม: O(k) สำหรับลิสต์ merged ที่เก็บคำตอบครบทั้งชุด
ข้อดี: เหตุผลตรงไปตรงมา เหมาะกับการเรียนเรื่อง merge และนำแนวคิดไปใช้กับตัวอ่านข้อมูลทีละรายการได้
ข้อเสีย/edge cases: มีลิสต์ขนาดเต็มเพิ่มขึ้นอีกชุด ถ้าใช้ nums1 = merged จะเปลี่ยนแค่ชื่อตัวแปรในฟังก์ชัน จึงต้องใช้ slice เพื่อแก้ลิสต์เดิม; อินพุตฝั่งว่างถูกจัดการโดยลูปเก็บส่วนที่เหลือ

เวลาเจอค่าซ้ำ โค้ดเลือกฝั่งแรกก่อนด้วย <= แต่ทั้งสองตัวต้องอยู่ในคำตอบ ไม่ใช่ตัดซ้ำแบบเซตครับ ส่วนค่าติดลบก็เปรียบเทียบตามปกติ ไม่มีเงื่อนไขว่าข้อมูลต้องเป็นบวก

ฮูกถอยกางปีก “โต๊ะใหม่สะอาดดี แต่ท้ายโต๊ะเดิมก็ยังว่างอยู่นะ” น้องโต๊ะตอบทันที “ถ้าเขียนด้านหน้า จะทับของที่ยังไม่ได้อ่าน!” ประเด็นนี้เองที่ทำให้วิธีถัดไปต้องเปลี่ยนทิศทาง

วิธีที่ 3: นกฮูกเดินถอยหลัง — สามตัวชี้เติมจากท้าย

ฮูกถอยตั้ง i = m-1 ที่ข้อมูลจริงตัวสุดท้ายในแถวแรก ตั้ง j = n-1 ที่ท้ายแถวสอง และตั้ง k = m+n-1 ที่ช่องเขียนสุดท้าย จากนั้นเลือกค่าที่มากกว่าระหว่างสองท้ายแถวไปใส่ช่อง k แล้วถอยตัวชี้ครับ

ทิศนี้ปลอดภัยเพราะตอนที่ nums2 ยังเหลือ จะมีช่องเขียนอยู่ทางขวาของข้อมูล nums1 ที่ยังไม่อ่านเสมอ เริ่มต้นช่องเขียนห่างจาก i อยู่ n ช่อง ถ้าหยิบจากแถวแรก ทั้ง k และ i ถอยพร้อมกัน ระยะห่างจึงเท่าเดิม ถ้าหยิบจากแถวสอง ระยะจะลดลงพร้อมจำนวนข้อมูลฝั่งนั้น

nums1 = [1, 3, 0, 0]    nums2 = [2, 4]
            i     k                  j
เลือก 4 → [1, 3, 0, 4]
เลือก 3 → [1, 3, 3, 4]
เลือก 2 → [1, 2, 3, 4]
เหลือ 1 อยู่ถูกที่แล้ว จบได้เลย

ภาพที่ดูเหมือนมีเลขซ้ำระหว่างทางไม่ใช่ข้อผิดพลาด ช่องที่เขียนเสร็จแล้วคือคำตอบ ส่วนข้อมูลจริงที่ยังไม่อ่านถูกกำหนดด้วยตัวชี้ เราไม่จำเป็นต้องล้างตำแหน่งเก่าทุกครั้งครับ

เหตุผลที่วนแค่ while j >= 0 คือถ้าแถวสองหมด ข้อมูลแถวแรกที่เหลือก็อยู่ถูกที่อยู่แล้ว แต่ถ้าแถวแรกหมดก่อน ต้องย้ายแถวสองที่เหลือต่อ เงื่อนไข i >= 0 จึงต้องอยู่หน้าการอ่าน nums1[i] เพื่อไม่เผลออ่านดัชนีติดลบซึ่ง Python ยอมให้เข้าถึงท้ายลิสต์

เวลา: O(k) ในกรณีแย่สุด แต่ถ้า n=0 จะจบทันที เพราะไม่มีอะไรต้องย้ายเข้ามา
หน่วยความจำเพิ่ม: O(1) มีเพียงเลขตำแหน่งไม่กี่ตัว ไม่สร้างภาชนะตามขนาดอินพุต
ข้อดี: ใช้ประโยชน์จากช่องว่างที่โจทย์เตรียมมา ได้ทั้งเวลาเชิงเส้นและพื้นที่เพิ่มคงที่
ข้อเสีย/edge cases: ต้องระวังจุดเริ่มตัวชี้และการลดตำแหน่ง เมื่อ m=0 ให้คัดลอกจากแถวสองจนหมด และเมื่อค่าเท่ากัน เลือกฝั่งใดก็ได้สำหรับโจทย์จำนวนเต็มนี้

บารอนเคาะโต๊ะเบา ๆ “อธิบายได้แล้วว่าของไม่โดนทับ ต่อไปขอดูว่าทุกตัวคืนคำตอบลงชามใบเดิมจริงไหม” ผมจึงให้เทสต์ตรวจทั้งค่า ผลข้างเคียง และตัวลิสต์ที่ถูกแก้ครับ

โค้ดทุกวิธี พร้อมเทสต์

เซฟบล็อกนี้เป็น solutions.py แล้วรัน python3 -I -B solutions.py ได้เลย -I แยกสภาพแวดล้อมของ Python และ -B ไม่สร้างไฟล์ bytecode เทสต์ใช้กรณีปกติ ค่าซ้ำ ค่าติดลบ ศูนย์จริง ฝั่งใดฝั่งหนึ่งว่าง และทั้งสองฝั่งว่าง ซึ่งกรณีสุดท้ายเพิ่มไว้ตรวจความทนของฟังก์ชันนอกเหนือจากอินพุตที่โจทย์กำหนดครับ

import unittest


def elephant(nums1, m, nums2, n):
    nums1[m:] = nums2
    nums1.sort()


def rabbit(nums1, m, nums2, n):
    merged = []
    i = j = 0
    while i < m and j < n:
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    while i < m:
        merged.append(nums1[i])
        i += 1
    while j < n:
        merged.append(nums2[j])
        j += 1
    nums1[:] = merged


def owl(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1


ALL = [elephant, rabbit, owl]


class MergeTests(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [
            ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3),
            ([1], 1, [], 0),
            ([0], 0, [1], 1),
            ([], 0, [], 0),
            ([0, 0, 0], 0, [-3, 0, 4], 3),
            ([-5, -2, 0, 0, 0], 3, [-4, -2], 2),
            ([2, 2, 0, 0], 2, [2, 2], 2),
            ([4, 5, 6, 0, 0, 0], 3, [1, 2, 3], 3),
            ([1, 2, 0, 0], 2, [3, 4], 2),
            ([0, 0], 1, [0], 1),
        ]
        for fn in ALL:
            for initial, m, second, n in cases:
                with self.subTest(method=fn.__name__, case=initial):
                    nums1, nums2 = initial.copy(), second.copy()
                    alias = nums1
                    expected = sorted(initial[:m] + second)
                    result = fn(nums1, m, nums2, n)
                    self.assertEqual(nums1, expected)
                    self.assertIs(nums1, alias)
                    self.assertEqual(nums2, second)
                    self.assertIsNone(result)


if __name__ == "__main__":
    unittest.main()

ทั้งสามฟังก์ชันแก้ nums1 แล้วคืน None เทสต์ยังตรวจว่า nums2 ไม่เปลี่ยน และตัวแปรที่อ้างลิสต์เดิมเห็นผลลัพธ์เดียวกัน การใช้ sorted() ในเทสต์เป็นเพียงตัวสร้างคำตอบอ้างอิง ไม่ใช่ส่วนหนึ่งของวิธีนกฮูกหรือกระต่ายครับ บล็อกนี้รันผ่านจริงด้วยคำสั่งข้างต้น

Benchmark ที่รันจริง (20 ต.ค. 2026 บนเครื่องนี้)

เครื่องที่รันใช้ Python 3.14.7 ตามผล python3 -V และสถาปัตยกรรม x86_64 จาก platform.machine() วัดด้วย timeit ของ Python ใช้ timeit.repeat จำนวน 5 ชุด เลือกเวลารวมที่น้อยที่สุดแล้วหารด้วยจำนวนรอบ เพื่อรายงานมิลลิวินาทีต่อการรวมหนึ่งครั้ง

ข้อมูลแถวแรกเป็นเลขคู่จากศูนย์ แถวสองเป็นเลขคี่จากหนึ่ง ทำให้ผลลัพธ์ต้องสลับสองฝั่งตลอด กำหนด m=n และให้ nums1 มีศูนย์สำรองตามจำนวน n สร้างข้อมูลตั้งต้นไว้นอกช่วงจับเวลา แต่ในแต่ละรอบจับเวลารวม first.copy() เพื่อให้ทุกวิธีเริ่มด้วยลิสต์ใหม่เหมือนกัน แล้วจึงเรียกฟังก์ชัน ไม่มีการนำผลที่รวมเสร็จแล้วมาวัดซ้ำครับ

ข้อมูลรวม `m+n`	`m`, `n`	รอบต่อชุด	ช้างเทกอง (ms)	กระต่ายจองโต๊ะใหม่ (ms)	นกฮูกเดินถอยหลัง (ms)
2,000	1,000, 1,000	200	0.014	0.079	0.086
20,000	10,000, 10,000	50	0.144	0.852	0.937

ช้างชนะทั้งสองขนาดในรอบวัดนี้ สอดคล้องกับการที่ตัวเรียงของ CPython ทำงานส่วนหลักใน C และรับข้อมูลที่มีช่วงเรียงอยู่แล้ว ขณะที่อีกสองวิธีวนลูปและเปรียบเทียบผ่านโค้ด Python กระต่ายเร็วกว่านกฮูกเล็กน้อยในข้อมูลชุดนี้ แต่การวัดนี้ยังแยกไม่ได้ว่าต้นทุนย่อยส่วนใดสร้างช่องว่างนั้นมากที่สุด ค่าเหล่านี้เป็นของเครื่องนี้และรูปแบบอินพุตนี้เท่านั้น ไม่ใช่หลักฐานว่าการเรียงใหม่จะชนะทุกกรณี หรือว่าพื้นที่เพิ่มของมันลดลงเป็นค่าคงที่

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด	นกฮูกเดินถอยหลัง	แสดงเหตุผลว่าทำไมไม่ทับข้อมูล และอธิบายเวลาเชิงเส้นพร้อมพื้นที่เพิ่มคงที่ได้
โค้ดงานจริงที่เป็น hot path (production)	ทดลองช้างเทกองก่อน ถ้ามีงบหน่วยความจำ	hot path คือส่วนที่ถูกเรียกบ่อยจนกระทบเวลารวม ช้างเร็วสุดในข้อมูลที่วัด แต่ต้องวัดด้วยข้อมูลจริงก่อนตัดสินใจ
สอนมือใหม่	กระต่ายจองโต๊ะใหม่	เห็นการหยิบหัวคิวชัดเจน แยกแนวคิดการรวมออกจากปัญหาการเขียนทับ
หน่วยความจำตึง	นกฮูกเดินถอยหลัง	ไม่สร้างลิสต์คำตอบเพิ่ม และใช้ช่องสำรองเดิมได้ครบ
ข้อมูลมาเป็น stream ทีละก้อน	ดัดแปลงกระต่ายเป็นตัวอ่านแล้วส่งออกทีละค่า	ใช้แนวคิดเทียบหัวคิวได้ แต่ต้องรู้ว่าแต่ละสายเรียงต่อเนื่องข้ามก้อนด้วย และไม่ใช่ฟังก์ชันที่สร้างลิสต์เต็มข้างบนตรง ๆ

stream คือข้อมูลที่ทยอยอ่านเข้ามา ไม่ได้มีทั้งหมดอยู่ในลิสต์พร้อมกัน ถ้าข้อมูลแต่ละก้อนเรียงเฉพาะภายในก้อน แต่ก้อนถัดไปมีค่าน้อยกว่าย้อนมาได้ เราจะปล่อยคำตอบสุดท้ายทันทีจากหัวคิวไม่ได้ ต้องมีเงื่อนไขเพิ่มเกี่ยวกับลำดับของทั้งสายครับ

ค่าเริ่มต้นภายใต้กติกาของโจทย์: เลือกนกฮูกเดินถอยหลัง เพราะรวมลง nums1 เดิมด้วยเวลา O(m+n) และหน่วยความจำเพิ่ม O(1); ถ้าโจทย์งานจริงยอมแลกพื้นที่เพื่อความเร็ว ค่อยพิจารณาช้างจากผลวัดของงานนั้น

บารอนสรุป

บารอนกระชับปกเสื้อโค้ตแล้วประกาศว่า “ถ้วยเวลาเครื่องนี้เป็นของช้างเทกอง สองขนาดที่วัดได้ชนะทั้งคู่ครับ” เขายกปีกครีบให้นกฮูกต่อ “แต่ถ้วยคำตอบหลักของโจทย์ ผมให้นกฮูกเดินถอยหลัง เพราะใช้ที่เพิ่มคงที่และอธิบายได้ว่าข้อมูลไม่ถูกทับ” กระต่ายรับหน้าที่พาเพื่อนใหม่เข้าใจการรวมคิว ด้วยขั้นตอนเดินหน้าที่อ่านตามง่าย บารอนปิดสมุดว่า “เลือกให้ตรงข้อจำกัด แล้วค่อยใช้เวลาที่วัดจริงช่วยตัดสิน อย่าให้ความเร็วของข้อมูลชุดเดียวกลบต้นทุนพื้นที่นะครับ”

Recap

แยกข้อมูลจริง m ช่องแรกออกจากศูนย์สำรองให้ถูกก่อนเริ่ม
ลองเทข้อมูลท้ายแถวแล้วเรียง และอธิบายพื้นที่ช่วยที่อาจใช้เพิ่ม
เขียนวิธีสองตัวชี้เดินหน้า แล้วคัดลอกคำตอบกลับด้วย slice
วาด i, j, k ของวิธีถอยหลัง และไล่กรณีแถวแรกหมดก่อน
รันเทสต์ทั้งค่าซ้ำ ค่าติดลบ ศูนย์จริง และฝั่งว่าง
วัดเวลาแบบเริ่มจากข้อมูลใหม่ทุกครั้ง แล้วเลือกวิธีตามงบเวลาและหน่วยความจำ