22.2 merge sort

หน้า 13.3 วัดแล้วว่า bubble selection และ insertion sort โตตาม N² ข้อมูลแสนตัวใช้หลายวินาที ส่วน qsort กับ sort เรียงได้ในเสี้ยววินาที หน้านี้เขียนวิธีเรียงที่เร็วระดับเดียวกันขึ้นเองด้วย divide and conquer ชื่อ merge sort เรียงครึ่งซ้าย เรียงครึ่งขวา แล้วรวมสองครึ่งที่เรียงแล้วเข้าด้วยกัน มี sort ให้ใช้อยู่แล้วก็ยังต้องรู้ เพราะขั้นรวมของ merge sort คือเครื่องมือของโจทย์อีกหลายแบบ เช่น นับคู่สลับในหน้าถัดไป และข้อสอบค่ายชอบให้ไล่ขั้นตอนของมันด้วยมือ

รวมสองแถวที่เรียงแล้ว

ขั้นรวมเป็นหัวใจของวิธีนี้ เริ่มจากปัญหาเล็กๆ ป้ายรถเมล์มีรถสองสายผ่าน แต่ละสายมีตารางเวลามาถึงที่เรียงแล้ว (นาทีหลัง 6 โมงเช้า) อยากได้ตารางเดียวที่เรียงตามเวลา ไม่ต้องเรียงใหม่ทั้งหมด ใช้สองตัวชี้ i ชี้คันแรกของสาย A ที่ยังไม่ได้ใส่ตาราง j ชี้ของสาย B ทุกรอบเทียบสองคันที่ชี้อยู่ คันที่มาก่อนคือคันที่มาเร็วที่สุดในบรรดาทุกคันที่เหลือแน่นอน เพราะทั้งสองสายเรียงแล้ว หยิบคันนั้นใส่ตาราง แล้วเลื่อนตัวชี้ของสายนั้น

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> line_a(n), line_b(m);
    for (int i = 0; i < n; i++) {
        cin >> line_a[i];
    }
    for (int j = 0; j < m; j++) {
        cin >> line_b[j];
    }
    vector<int> timetable;
    int i = 0, j = 0;
    while (i < n && j < m) { // (1)!
        if (line_a[i] <= line_b[j]) {
            cout << "A " << line_a[i] << " vs B " << line_b[j] << ": take A\n";
            timetable.push_back(line_a[i]);
            i++;
        } else {
            cout << "A " << line_a[i] << " vs B " << line_b[j] << ": take B\n";
            timetable.push_back(line_b[j]);
            j++;
        }
    }
    while (i < n) { // (2)!
        timetable.push_back(line_a[i]);
        i++;
    }
    while (j < m) {
        timetable.push_back(line_b[j]);
        j++;
    }
    for (int k = 0; k < n + m; k++) {
        cout << timetable[k] << (k == n + m - 1 ? '\n' : ' ');
    }
    return 0;
}

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

4 5
5 12 20 31
7 8 25 40 41

A 5 vs B 7: take A
A 12 vs B 7: take B
A 12 vs B 8: take B
A 12 vs B 25: take A
A 20 vs B 25: take A
A 31 vs B 25: take B
A 31 vs B 40: take A
5 7 8 12 20 25 31 40 41

ทุกครั้งที่เทียบ มีหนึ่งคันได้ลงตาราง รถเก้าคันจึงเทียบไม่เกินแปดครั้ง ครั้งนี้เทียบแค่เจ็ดครั้ง เพราะพอสาย A หมด คันที่ 40 กับ 41 ของสาย B ต่อท้ายได้เลย การรวมสองแถวยาว n กับ m จึงเป็น O(n + m) ส่วนเงื่อนไข <= ทำให้ถ้ามาถึงพร้อมกัน คันของสาย A ได้ลงตารางก่อน รายละเอียดนี้จะสำคัญในหัวข้อ stable ข้างล่าง

เรียงด้วยการแบ่งแล้วรวม

ถ้าอาเรย์ทั้งสองครึ่งเรียงอยู่แล้ว ขั้นรวมทำให้ทั้งอาเรย์เรียงได้ใน O(N) แล้วครึ่งแต่ละครึ่งจะเรียงได้ยังไง ก็ใช้วิธีเดียวกัน แบ่งครึ่งอีก จนเหลือช่วงยาวหนึ่งช่อง ซึ่งเรียงอยู่แล้วโดยไม่ต้องทำอะไร ครบสามขั้นของหน้า 22.1

แบ่ง ช่วง [lo, hi) ที่ mid
แก้ย่อย merge sort ครึ่งซ้ายกับครึ่งขวา
รวม ครึ่งที่เรียงแล้วสองครึ่ง ใส่ลงอาเรย์พัก temp แล้วคัดลอกกลับ

คะแนนสอบย่อยของนักเรียน 8 คน โปรแกรมพิมพ์ผลทุกครั้งที่รวมเสร็จ

#include <bits/stdc++.h>
using namespace std;

void merge_sort(vector<int> &a, vector<int> &temp, int lo, int hi) // (1)!
{
    if (hi - lo <= 1) {
        return;
    }
    int mid = (lo + hi) / 2;
    merge_sort(a, temp, lo, mid);
    merge_sort(a, temp, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) {
            temp[k] = a[i];
            i++;
        } else {
            temp[k] = a[j];
            j++;
        }
        k++;
    }
    while (i < mid) {
        temp[k] = a[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = a[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) { // (2)!
        a[t] = temp[t];
    }
    cout << "merge [" << lo << ", " << mid << ") + [" << mid << ", " << hi << "):";
    for (int t = lo; t < hi; t++) {
        cout << ' ' << a[t];
    }
    cout << '\n';
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> temp(n); // (3)!
    merge_sort(a, temp, 0, n);
    return 0;
}

ส่งทั้ง a และ temp แบบ reference ตามบทที่ 15 ไม่มีการคัดลอก vector ตอนเรียก
ผลที่รวมแล้วอยู่ใน temp ช่อง lo ถึง hi - 1 ต้องคัดลอกกลับมาที่ a ชั้นที่เรียกมาจะได้เห็นครึ่งนี้เรียงแล้ว
จองอาเรย์พักครั้งเดียวขนาด n แล้วใช้ร่วมกันทุกชั้น แต่ละชั้นใช้เฉพาะช่องในช่วงของตัวเอง ซึ่งไม่ทับกับช่วงที่ชั้นอื่นกำลังใช้ ดูว่าทำไมห้ามจองใหม่ทุกครั้งในส่วนลองทำให้พัง

8
38 27 43 3 9 82 10 55

merge [0, 1) + [1, 2): 27 38
merge [2, 3) + [3, 4): 3 43
merge [0, 2) + [2, 4): 3 27 38 43
merge [4, 5) + [5, 6): 9 82
merge [6, 7) + [7, 8): 10 55
merge [4, 6) + [6, 8): 9 10 55 82
merge [0, 4) + [4, 8): 3 9 10 27 38 43 55 82

การรวมเกิดขึ้นในขากลับ ครึ่งซ้ายทั้งหมดเสร็จก่อน (สามบรรทัดแรก) แล้วจึงถึงครึ่งขวา (สามบรรทัดถัดมา) บรรทัดสุดท้ายรวมสองครึ่งที่เรียงแล้ว ภาพนี้แสดงทั้งขาแบ่งและขารวม

ขาแบ่งไม่ได้ย้ายข้อมูลเลย แค่คำนวณ mid งานจริงทั้งหมดอยู่ในขารวม แถวสีน้ำเงินแต่ละแถวคือการรวมหนึ่งชั้นของต้นไม้

ทำไมเป็น O(N log N)

ใช้วิธีนับของหน้า 18.3 รวมงานทีละชั้นของต้นไม้ การรวมช่วงยาว hi - lo ใช้งานราว hi - lo ครั้ง (หยิบใส่ temp หนึ่งครั้งต่อหนึ่งตัว) โปรแกรมนี้จดงานของการรวมแยกตามความลึก ข้อมูล 1000 ตัวสร้างจากสูตร i * 7919 % n แบบหน้า 13.3 ซึ่งได้ 0 ถึง 999 ครบทุกตัวแต่สลับลำดับ

#include <bits/stdc++.h>
using namespace std;

vector<long long> work(40, 0);

void merge_sort(vector<int> &a, vector<int> &temp, int lo, int hi, int depth)
{
    if (hi - lo <= 1) {
        return;
    }
    int mid = (lo + hi) / 2;
    merge_sort(a, temp, lo, mid, depth + 1);
    merge_sort(a, temp, mid, hi, depth + 1);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) {
            temp[k] = a[i];
            i++;
        } else {
            temp[k] = a[j];
            j++;
        }
        k++;
    }
    while (i < mid) {
        temp[k] = a[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = a[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        a[t] = temp[t];
    }
    work[depth] += hi - lo; // (1)!
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = (long long)i * 7919 % n; // (2)!
    }
    vector<int> temp(n);
    merge_sort(a, temp, 0, n, 0);
    long long total = 0;
    for (int d = 0; d < 40 && work[d] > 0; d++) {
        cout << "depth " << d << ": " << work[d] << '\n';
        total += work[d];
    }
    cout << "total = " << total << '\n';
    return 0;
}

ชั้นที่ depth หยิบของใส่ temp เพิ่มอีก hi - lo ตัว
cast เป็น long long ก่อนคูณ เพราะถ้า n เป็นล้าน i * 7919 ถึงราว 8 × 10⁹ เกิน int

depth 0: 1000
depth 1: 1000
depth 2: 1000
depth 3: 1000
depth 4: 1000
depth 5: 1000
depth 6: 1000
depth 7: 1000
depth 8: 1000
depth 9: 976
total = 9976

ทุกชั้นทำงาน 1000 ครั้งเท่ากับ N เพราะช่วงในชั้นเดียวกันไม่ทับกันและครอบคลุมทุกช่อง ชั้นสุดท้ายได้ 976 เพราะบางช่วงเหลือช่องเดียวไปก่อนแล้ว 1000 ไม่ใช่กำลังของสองพอดี จำนวนชั้นคือ 10 ซึ่งคือ log₂ 1000 ปัดขึ้น งานรวมจึงราว N × log₂ N ได้ 9976 ใกล้กับ 1000 × 9.97 = 9966 ป้อน 1000000 ได้ 20 ชั้นและงานรวม 19951424 เป็น O(N log N) ตามแถวที่สี่ของตารางในหน้า 22.1

เทียบกับ insertion sort ที่เทียบเฉลี่ยราว N² / 4 ครั้งกับข้อมูลสุ่มตามหน้า 13.3 ที่ N เป็นแสน คือ 2.5 × 10⁹ ครั้ง ส่วน merge sort ทำงานราว 1.7 × 10⁶ ครั้ง ต่างกันกว่าพันเท่า และไม่ว่าข้อมูลจะเรียงมาแล้ว เรียงกลับ หรือสุ่ม merge sort ก็แบ่งแบบเดิมทุกครั้ง จึงเป็น O(N log N) เสมอ

เร็วขึ้นแค่ไหน

โปรแกรมจับเวลาใช้ฟังก์ชัน merge_sort แบบเดียวกับข้างบนแต่ตัดส่วนที่พิมพ์ออก ข้อมูลสร้างด้วย mt19937 ตัวสุ่มของ C++ ที่ใช้ในหน้า 20.1 ได้เลข 0 ถึง 10⁹ จาก seed ตายตัว แล้วจับเวลาด้วย clock() เฉพาะช่วงที่เรียง วัดแบบเดียวกับหน้า 22.1 insertion sort กับ sort ใช้ main เดียวกัน เปลี่ยนแค่บรรทัดที่เรียก

int main()
{
    int n;
    cin >> n;
    mt19937 rng(2569);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = rng() % 1000000000;
    }
    vector<int> temp(n);
    clock_t start = clock();
    merge_sort(a, temp, 0, n);
    clock_t end = clock();
    cout << "first = " << a[0] << ", last = " << a[n - 1] << '\n';
    cout << "time = " << fixed << setprecision(3) << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

วิธี	N	Code::Blocks (`-Wall`)	`-O2`
insertion sort O(N²)	10,000	0.084 วินาที	0.008 วินาที
insertion sort O(N²)	100,000	9.314 วินาที	0.765 วินาที
merge sort O(N log N)	10,000	0.001 วินาที	0.000 วินาที
	100,000	0.016 วินาที	0.006 วินาที
	1,000,000	0.211 วินาที	0.072 วินาที
`sort`	10,000	0.001 วินาที	0.000 วินาที
	100,000	0.016 วินาที	0.004 วินาที
	1,000,000	0.196 วินาที	0.048 วินาที

N เพิ่มสิบเท่า insertion sort ช้าลงราวร้อยเท่า ส่วน merge sort ช้าลงราวสิบกว่าเท่า ตรงกับ N log N ที่ N เพิ่มสิบเท่า log N เพิ่มแค่ราว 1.2 เท่า insertion sort ที่ล้านตัวจะใช้เป็นนาที (ประมาณจากตาราง ไม่ได้วัดจริง)
insertion sort แบบ Code::Blocks ที่แสนตัวใช้ 9.3 วินาที ช้ากว่า 2.4 วินาทีในหน้า 13.3 เพราะโปรแกรมนี้ใช้ vector ถ้าไม่เปิด -O2 การอ่านเขียนทุกช่องของ vector เป็นการเรียกฟังก์ชันจริงๆ แบบ push_back ในหน้า 16.2 พอเปิด -O2 ก็ใกล้กับในหน้า 13.3
merge sort ที่เขียนเองเร็วพอๆ กับ sort แบบ Code::Blocks และช้ากว่าราว 1.5 เท่าแบบ -O2 เรียงล้านตัวได้ในเสี้ยววินาทีทั้งคู่ ในการแข่งขันใช้ sort เมื่อแค่ต้องการให้เรียง เขียน merge sort เองเมื่อต้องทำอะไรเพิ่มระหว่างรวม แบบหน้าถัดไป

หน่วยความจำและ stable

ใช้หน่วยความจำเพิ่ม O(N) สำหรับ temp ข้อมูลล้านตัวต้องมีอีกล้านช่อง ต่างจาก insertion sort ที่เรียงในอาเรย์เดิม
stable ตามความหมายในหน้า 13.4 ค่าที่เท่ากันอยู่ตามลำดับเดิม เพราะเงื่อนไข a[i] <= a[j] หยิบจากครึ่งซ้ายก่อนเมื่อเท่ากัน และครึ่งซ้ายคือตัวที่มาก่อนในลำดับเดิมเสมอ ถ้าเปลี่ยนเป็น < ก็ยังเรียงถูก แต่เสียความ stable ไป stable_sort ในหน้า 16.4 ก็ใช้วิธีแบบ merge sort ข้างใน
ลึกแค่ราว log₂ N ชั้น ตามหน้า 22.1 ล้านตัวลึก 20 ชั้น ไม่มีปัญหาเรื่อง stack

ลองทำให้พัง

แบบที่ 1 ลืมเทส่วนที่เหลือของครึ่งซ้าย

เขียนลูปเทส่วนที่เหลือไว้แค่ฝั่งขวา เพราะคิดว่าเหลือแค่ฝั่งเดียวก็พอ

#include <bits/stdc++.h>
using namespace std;

void merge_sort(vector<int> &a, vector<int> &temp, int lo, int hi)
{
    if (hi - lo <= 1) {
        return;
    }
    int mid = (lo + hi) / 2;
    merge_sort(a, temp, lo, mid);
    merge_sort(a, temp, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) {
            temp[k] = a[i];
            i++;
        } else {
            temp[k] = a[j];
            j++;
        }
        k++;
    }
    while (j < hi) {
        temp[k] = a[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        a[t] = temp[t];
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> temp(n);
    merge_sort(a, temp, 0, n);
    for (int i = 0; i < n; i++) {
        cout << a[i] << (i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

8
38 27 43 3 9 82 10 55

3 0 3 0 9 10 55 55

มีเลข 0 ที่ไม่เคยอยู่ในข้อมูล และ 27 38 43 82 หายไป ตั้งแต่การรวมครั้งแรก [38] + [27] หยิบ 27 จากขวาแล้วขวาก็หมด 38 ที่ค้างอยู่ทางซ้ายไม่ได้ลง temp ช่องนั้นจึงเป็นค่าเดิมของ temp คือ 0 หรือของที่ค้างจากการรวมครั้งก่อน แล้วถูกคัดลอกกลับไปทับข้อมูลจริง ตัวอย่างที่บังเอิญมีครึ่งซ้ายหมดก่อนทุกครั้งจะผ่าน เช่น ข้อมูลที่เรียงมาแล้ว จึงต้องทดสอบด้วยข้อมูลเรียงกลับด้านด้วย

แบบที่ 2 จองอาเรย์พักใหม่ทุกครั้ง

อยากให้ฟังก์ชันรับแค่ a จึงย้ายการจอง temp เข้าไปไว้ในฟังก์ชัน ขนาดเท่าทั้งอาเรย์

void merge_sort(vector<int> &a, int lo, int hi)
{
    if (hi - lo <= 1) {
        return;
    }
    int mid = (lo + hi) / 2;
    vector<int> temp(a.size());
    merge_sort(a, lo, mid);
    merge_sort(a, mid, hi);
    // รวมเหมือนเดิม
}

ผลยังเรียงถูก แต่เวลาที่วัดแบบเดียวกับตารางข้างบนเป็นแบบนี้

N	Code::Blocks (`-Wall`)	`-O2`
10,000	0.172 วินาที	0.097 วินาที
100,000	11.461 วินาที	7.037 วินาที

ช้ากว่า insertion sort เสียอีก vector<int> temp(a.size()) ไม่ได้ฟรี มันจองที่ N ช่องแล้วเติม 0 ให้ทุกช่อง ใช้เวลา O(N) และเกิดขึ้นทุกครั้งที่แบ่ง ซึ่งมี N - 1 ครั้งตามหน้า 22.1 รวมเป็น O(N²) ความเร็วของ merge sort หายหมด งานที่ทำในแต่ละครั้งที่เรียกต้องเป็นสัดส่วนกับขนาดของช่วงนั้น ไม่ใช่ขนาดของทั้งอาเรย์ จองครั้งเดียวใน main แล้วส่ง reference เข้าไปแบบโปรแกรม merge-sort

สรุป

รวมสองแถวที่เรียงแล้วด้วยสองตัวชี้ หยิบตัวที่น้อยกว่าทีละตัว แล้วเทส่วนที่เหลือให้ครบทั้งสองฝั่ง ใช้เวลา O(n + m)
merge sort แบ่งครึ่ง เรียงแต่ละครึ่ง แล้วรวม ทุกชั้นของต้นไม้ทำงาน N ครั้ง มี log₂ N ชั้น จึงเป็น O(N log N) เสมอ ไม่ขึ้นกับข้อมูล
บนเครื่องที่วัด แสนตัวใช้ 0.009 วินาทีแบบ -O2 ส่วน insertion sort ใช้ 0.765 วินาที
ใช้หน่วยความจำเพิ่ม O(N) และเป็น stable เมื่อใช้ <= หยิบฝั่งซ้ายก่อน
จองอาเรย์พักครั้งเดียว ห้ามจองขนาด N ในทุกครั้งที่เรียก และทดสอบด้วยข้อมูลเรียงกลับด้าน