CREATE OR REPLACE PACKAGE PG_MERGESORT IS

  -- Author  : wealth_khb@126.com

  -- 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;