pl/sql 实现归并算法 (合并插入法的优化)

CREATE OR REPLACE PACKAGE PG_MERGESORT IS

  -- Author  : [e-mail]
  -- Created : 2009-10-20 10:09:16
  -- Purpose : 

  TYPE EMP_SSN_ARRAY IS TABLE OF NUMBER INDEX BY BINARY_INTEGER; ---声明数组类型
  BEST_EMPLOYEES EMP_SSN_ARRAY; ----数组

  BIG_UPPER    INTEGER;
  MIDDLE_VALUE NUMBER; ---------最大
  -- Public function and procedure declarations
  ------初始化过程
  PROCEDURE PRO_MERGESORT(UPPER_N IN NUMBER);
  FUNCTION FUN_MERGESORT(UPPER_ARRAY IN EMP_SSN_ARRAY) RETURN EMP_SSN_ARRAY;
  FUNCTION FUN_MERGE(LEFT_ARRAY  IN EMP_SSN_ARRAY,
                     RIGHT_ARRAY IN EMP_SSN_ARRAY) RETURN EMP_SSN_ARRAY;
END PG_MERGESORT;
（包体部分）

CREATE OR REPLACE PACKAGE BODY PG_MERGESORT IS

  PROCEDURE PRO_MERGESORT(UPPER_N IN NUMBER) IS
    V_EMP_SSN_ARRAY EMP_SSN_ARRAY;
    V_L             INTEGER;
  BEGIN
    V_L       := 1;
    BIG_UPPER := UPPER_N; ---最大长度
    ------对数组赋值
    FOR X IN 1 .. BIG_UPPER LOOP
      BEST_EMPLOYEES(X) := X * (DBMS_RANDOM.VALUE(X, 1));
    END LOOP;
    ---返回
     DBMS_OUTPUT.PUT_LINE('排序前'||V_EMP_SSN_ARRAY.COUNT||'个');
    FOR P IN BEST_EMPLOYEES.FIRST .. BEST_EMPLOYEES.LAST LOOP
      DBMS_OUTPUT.PUT_LINE(BEST_EMPLOYEES(P));
    END LOOP;
    V_EMP_SSN_ARRAY := FUN_MERGESORT(BEST_EMPLOYEES);
    ---递归调用返回结果左边
      DBMS_OUTPUT.PUT_LINE('结果输出'||V_EMP_SSN_ARRAY.COUNT||'个');
    FOR v_1 IN V_EMP_SSN_ARRAY.FIRST .. V_EMP_SSN_ARRAY.LAST LOOP
      DBMS_OUTPUT.PUT_LINE(V_EMP_SSN_ARRAY(v_1));
    END LOOP;

  END;
  -----------------------------------------------------
  FUNCTION FUN_MERGESORT(UPPER_ARRAY IN EMP_SSN_ARRAY) RETURN EMP_SSN_ARRAY IS
    V_UPPER     NUMBER(18, 0);
    V_MIDDLE    NUMBER(18, 0);
    V_VALUE     EMP_SSN_ARRAY;
    LEFT_ARRAY  EMP_SSN_ARRAY; ----数组
    RIGHT_ARRAY EMP_SSN_ARRAY; ----数组

  BEGIN

    --------

    V_UPPER := UPPER_ARRAY.COUNT;
    IF (UPPER_ARRAY.COUNT = 1 OR UPPER_ARRAY.COUNT = 0) THEN
      RETURN UPPER_ARRAY;
    END IF;

    V_MIDDLE := floor(UPPER_ARRAY.COUNT / 2);

    FOR X IN 1 .. V_MIDDLE LOOP
      LEFT_ARRAY(X) := UPPER_ARRAY(X);
      RIGHT_ARRAY(X) := UPPER_ARRAY(X + V_MIDDLE);
    END LOOP;

   IF (MOD(V_UPPER, 2) = 0) THEN
      NULL;
    ELSE
      LEFT_ARRAY(V_MIDDLE + 1) := UPPER_ARRAY(V_UPPER);
    END IF;

    LEFT_ARRAY  := FUN_MERGESORT(LEFT_ARRAY);
    RIGHT_ARRAY := FUN_MERGESORT(RIGHT_ARRAY);
    ----进行归并

    V_VALUE := FUN_MERGE(LEFT_ARRAY, RIGHT_ARRAY);
    RETURN V_VALUE;
  END;

  FUNCTION FUN_MERGE(LEFT_ARRAY  IN EMP_SSN_ARRAY,
                     RIGHT_ARRAY IN EMP_SSN_ARRAY) RETURN EMP_SSN_ARRAY IS
    V_EMP_SSN_ARRAY EMP_SSN_ARRAY;
    V_INT           INTEGER := 0;
    V_LEFT          INTEGER := 0;
    V_RIGHT         INTEGER := 0;
    V_LEFT_ARRAY    EMP_SSN_ARRAY;
    V_RIGHT_ARRAY   EMP_SSN_ARRAY;

  BEGIN
    V_LEFT_ARRAY  := LEFT_ARRAY;
    V_RIGHT_ARRAY := RIGHT_ARRAY;

    WHILE ((V_LEFT < V_LEFT_ARRAY.COUNT) AND
          (V_RIGHT < V_RIGHT_ARRAY.COUNT)) LOOP
      IF (V_LEFT_ARRAY(V_LEFT + 1) < V_RIGHT_ARRAY(V_RIGHT + 1)) THEN
        V_INT := V_INT + 1;
        V_LEFT := V_LEFT + 1;
        V_EMP_SSN_ARRAY(V_INT) := V_LEFT_ARRAY(V_LEFT);
      ELSE
        V_INT := V_INT + 1;
        V_RIGHT := V_RIGHT + 1;
        V_EMP_SSN_ARRAY(V_INT) := V_RIGHT_ARRAY(V_RIGHT);
      END IF;
    END LOOP;

    WHILE (V_LEFT < V_LEFT_ARRAY.COUNT) LOOP
      V_INT := V_INT + 1;
      V_LEFT := V_LEFT + 1;
      V_EMP_SSN_ARRAY(V_INT) := V_LEFT_ARRAY(V_LEFT);
    END LOOP;

    WHILE (V_RIGHT < V_RIGHT_ARRAY.COUNT) LOOP
      V_INT := V_INT + 1;
      V_RIGHT := V_RIGHT + 1;
      V_EMP_SSN_ARRAY(V_INT) := V_RIGHT_ARRAY(V_RIGHT);
    END LOOP;
    RETURN V_EMP_SSN_ARRAY;
  END;
END PG_MERGESORT;