前两天看到网上的排序算法谢了个归并排序的pl/sql的实现，今天看到网上有一些优化，增加了一个插入排序。现更新代码如下。
注释：window下把oracle 10.2.0.1 通过 9.2.0.8的客户端导出后，在用linux下的10.2.0.1的客户端导入到linux下的10.2.0.1的数据库时过程，函数，和包里面的汉字注释丢了（变成??）可能是字符集的问题，现在还没找到答案。



包头：
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;

  FUNCTION FUN_INTERLAY(UPPER_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;
  BEGIN
    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('排序前' || BEST_EMPLOYEES.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);
    /* V_EMP_SSN_ARRAY := FUN_INTERLAY(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 = 0 OR UPPER_ARRAY.COUNT = 1) THEN
      RETURN UPPER_ARRAY;
    END IF;
    IF (V_UPPER <= 10) THEN
      RETURN FUN_INTERLAY(UPPER_ARRAY);
   
   
    ELSE
    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);
    ----????
    END IF;
    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;

  FUNCTION FUN_INTERLAY(UPPER_ARRAY IN EMP_SSN_ARRAY) RETURN EMP_SSN_ARRAY IS
    V_UPPER_ARRAY EMP_SSN_ARRAY;
    V_INT         INTEGER;
    V_SMALL_TEMP  NUMBER;
    V_BIG_TEMP    NUMBER;
  BEGIN
    V_UPPER_ARRAY := UPPER_ARRAY;
    IF (V_UPPER_ARRAY.COUNT = 0 OR V_UPPER_ARRAY.COUNT = 1) THEN
      RETURN UPPER_ARRAY;
    END IF;
    FOR X IN 1 .. V_UPPER_ARRAY.COUNT - 1 LOOP
      -----如果数据小于前面的数据（进行循环插入） 
      IF (V_UPPER_ARRAY(X + 1) < V_UPPER_ARRAY(X)) THEN
        V_INT        := X + 1;
        V_SMALL_TEMP := V_UPPER_ARRAY(X + 1);
        V_BIG_TEMP   := V_UPPER_ARRAY(X);
        ---开始循环
        WHILE (V_UPPER_ARRAY(V_INT) < V_UPPER_ARRAY(V_INT - 1) AND
              V_INT > 2) LOOP
          V_BIG_TEMP := V_UPPER_ARRAY(V_INT - 1);
          V_SMALL_TEMP := V_UPPER_ARRAY(V_INT);
          V_UPPER_ARRAY(V_INT) := V_BIG_TEMP;
          V_UPPER_ARRAY(V_INT - 1) := V_SMALL_TEMP;
          V_INT := V_INT - 1;
        END LOOP;
 
      END IF;
    END LOOP;
    RETURN V_UPPER_ARRAY;
  END;

END PG_MERGESORT;