教科书MergeSort在SQL中的实现(Postgres)

WITH RECURSIVE merge_sort AS (
    -- 基础情况：只有一个元素的数组是有序的
    SELECT id, value
    FROM your_table
    WHERE id = (SELECT MIN(id) FROM your_table)
    
    UNION ALL
    
    -- 递归情况：合并两个有序的子数组
    SELECT m1.id, m1.value
    FROM merge_sort m1
    JOIN merge_sort m2 ON m1.id > m2.id
    WHERE NOT EXISTS (
        SELECT 1
        FROM merge_sort m3
        WHERE m3.id > m2.id AND m3.id < m1.id
    )
    ORDER BY m1.id, m2.id
)
SELECT id, value
FROM merge_sort
ORDER BY id;

CREATE INDEX idx_your_table_id ON your_table(id);

WITH RECURSIVE merge_sort AS (
    SELECT id, value
    FROM your_table
    WHERE id = (SELECT MIN(id) FROM your_table)
    
    UNION ALL
    
    SELECT m1.id, m1.value
    FROM merge_sort m1
    JOIN merge_sort m2 ON m1.id > m2.id
    WHERE NOT EXISTS (
        SELECT 1
        FROM merge_sort m3
        WHERE m3.id > m2.id AND m3.id < m1.id
    )
    ORDER BY m1.id, m2.id
)
SELECT id, value
FROM merge_sort
ORDER BY id;