CIYAWASAY

《Merge Sort》

n1←q-p+1

n2←r-q
△cerate arrays L(1..n1+1) and R(1..n2+1)

for i←1 to n1
   do L[i]←A[p+i-1]

for j←1 to n2
   do R[j]←A[q+j]

L[n1+1]←∞
R[n2+1]←∞
i←1
j←1
for k←p to r

   do if L[i]≦R[j]
      then A[k]←L[i]
         i←i+1
      else A[k]←R[j]
         j←j+1

if p<r

   then q←└(p+r)/2┘
   Merge-Sort(A,p,q)
   Merge-Sort(A,q+1,r)
   Merge(A,p,q,r)

void mergeSort(int[] Array, int p, int r){
   if( p < r ){
      int q = ( p + r )/2;
      mergeSort(Array, p, q);
      mergeSort(Array, q + 1, r);
      merge(Array, p, q, r);
   }
}

void merge(int[] Array, int p, int q, int r){
   int n1 = q - p + 1;
   int n2 = r - q;
   int[] L = new int[n1 + 1], R = new int[n2 + 1];
   int i, j;
   for(i = 0; i < n1; i++){
      L[i] = Array[p + i];
   }
   for(j = 0; j < n2; j++){
      R[j] = Array[q + j + 1];
   }
   L[n1] = R[n2] = Integer.MAX_VALUE;
   i = j = 0;
   for(int k = p; k <= r; k++){
      if(L[i] <= R[j]){
         Array[k] = L[i];
         i++;
      }
      else{
         Array[k] = R[j];
         j++;
      }
   }
}

void mergeSort(String[] Array){
   mergeSort(Array,0,Array.length-1);
}

void mergeSort(String[] Array, int p, int r) {
   if (p < r) {
      int q = (p + r) / 2;
      mergeSort(Array, p, q);
      mergeSort(Array, q + 1, r);
      merge(Array, p, q, r);
   }
}
   
void merge(String[] Array, int p, int q, int r) {
   int n1 = q - p + 1;
   int n2 = r - q;
   String[] L = new String[n1 + 1];
   String[] R = new String[n2 + 1];
   int i;
   int j;

   for (i = 0; i < n1; i++) {
      L[i] = Array[p + i].name;
   }

   for (j = 0; j < n2; j++) {
      R[j] = Array[q + j + 1].name;
   }

   L[n1] = R[n2] = new String(new char[]{Character.MAX_VALUE});
   i = j = 0;

   for (int k = p; k <= r; k++) {
      if (L[i].compareTo(R[j])<= 0) {
         Array[k].name = L[i];
         i++;
      } else {
         Array[k].name = R[j];
         j++;
      }
   }
}

# posted by SwanBear @ 00:01