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

Question

我正在尝试在 SQL 中实现教科书版本的 Mergesort，并尽量不使用 plpgsql。我只想使用 SQL。我使用 Postgres 作为我的数据库系统。我已经尝试了所有方法，但遗憾的是我无法取得进一步进展。

到目前为止，我的 Mergesort 函数如下所示:

CREATE OR REPLACE FUNCTION mergesort(A double precision[], p integer, r integer)
RETURNS double precision[] AS $$
    SELECT 
        CASE WHEN p < r THEN mergesort(A,p,floor((p+r)/2)::integer) 
             WHEN p < r THEN mergesort(A,floor((p+r)/2)::integer+1,r)
             WHEN p < r THEN merge(A,p,floor((p+r)/2)::integer,r)
             ELSE A
    END;
$$ LANGUAGE SQL;

我正在尝试获得类似此可执行文件并正常工作的东西(我知道在我的代码示例中 CASE 没有执行所有必要的三个调用，我还没有找到解决方案，不幸的是我没有'不知道如何将递归回调中归并排序的结果赋值给变量A)。

有人知道我该如何解决这个问题吗？

仅供引用:合并功能已经在 plpgsql 中实现并可执行。 (也许我会尝试在下一步中用 SQL 重写它)。

CREATE FUNCTION merge(A double precision[], p integer, q integer, r integer) 
RETURNS double precision[] AS $$
DECLARE
 n1 integer := q-p+1;
 n2 integer := r-q;
 L double precision[]; 
 Ri double precision[];
 g integer;
 h integer; 
BEGIN
 L = ARRAY[n1+1]; 
 Ri = ARRAY[n2+1];
 FOR i in 1..(n1+1) LOOP
    L[i] = A[p+i-1];
 END LOOP;
 FOR j in 1..n2+1 LOOP
    Ri[j] = A[q+j];
 END LOOP;
 L[n1+1] = 'Infinity';
 Ri[n2+1] = 'Infinity';
 g = 1;
 h = 1;
 FOR k in p..r LOOP
    IF L[g] <= Ri[h] THEN
        A[k] = L[g];
        g = g + 1;
    ELSE
        A[k] = Ri[h];
        h = h + 1; 
    END IF;
 END LOOP;
 RETURN A;
END;
$$ LANGUAGE plpgsql;

Answer 1

我现在已经找到并想与您分享解决方案。我现在选择了一种函数式算法，它比命令式算法更容易在 SQL 中实现。

合并排序:

CREATE OR REPLACE FUNCTION mergesort(A double precision[]) 
RETURNS double precision[] AS $$
    SELECT 
        CASE WHEN 1 < array_length(A,1) 
              THEN merge(mergesort(A[1:floor((1+array_length(A,1))/2)::integer]),
                         mergesort(A[floor((1+array_length(A,1))/2)::integer+1:array_length(A,1)]),
                         1,
                         1,
                         ARRAY[]::double precision[])
             ELSE A
        END;
$$ LANGUAGE SQL;

合并:

CREATE OR REPLACE FUNCTION merge(A1 double precision[],A2 double precision[], i integer, j integer,acc double precision[]) 
RETURNS double precision[] AS $$
    SELECT 
        CASE WHEN (i > array_length(A1,1) and j > array_length(A2,1)) THEN acc
             WHEN i > array_length(A1,1) THEN merge(A1,A2,i,j+1,array_append(acc,A2[j]))
             WHEN j > array_length(A2,1) THEN merge(A1,A2,i+1,j,array_append(acc,A1[i]))
             WHEN A1[i] <  A2[j] THEN merge(A1,A2,i+1,j,array_append(acc, A1[i]))
             WHEN A1[i] >= A2[j] THEN merge(A1,A2,i,j+1,array_append(acc, A2[j]))                
        END;
$$ LANGUAGE SQL;