MergeSort.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:3k
源码类别:

网格计算

开发平台:

Java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one
  3.  * or more contributor license agreements.  See the NOTICE file
  4.  * distributed with this work for additional information
  5.  * regarding copyright ownership.  The ASF licenses this file
  6.  * to you under the Apache License, Version 2.0 (the
  7.  * "License"); you may not use this file except in compliance
  8.  * with the License.  You may obtain a copy of the License at
  9.  *
  10.  *     http://www.apache.org/licenses/LICENSE-2.0
  11.  *
  12.  * Unless required by applicable law or agreed to in writing, software
  13.  * distributed under the License is distributed on an "AS IS" BASIS,
  14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15.  * See the License for the specific language governing permissions and
  16.  * limitations under the License.
  17.  */
  18. package org.apache.hadoop.util;
  19. import java.util.Comparator;
  20. import org.apache.hadoop.io.IntWritable;
  21. /** An implementation of the core algorithm of MergeSort. */
  22. public class MergeSort {
  23.   //Reusable IntWritables
  24.   IntWritable I = new IntWritable(0);
  25.   IntWritable J = new IntWritable(0);
  26.   
  27.   //the comparator that the algo should use
  28.   private Comparator<IntWritable> comparator;
  29.   
  30.   public MergeSort(Comparator<IntWritable> comparator) {
  31.     this.comparator = comparator;
  32.   }
  33.   
  34.   public void mergeSort(int src[], int dest[], int low, int high) {
  35.     int length = high - low;
  36.     // Insertion sort on smallest arrays
  37.     if (length < 7) {
  38.       for (int i=low; i<high; i++) {
  39.         for (int j=i;j > low; j--) {
  40.           I.set(dest[j-1]);
  41.           J.set(dest[j]);
  42.           if (comparator.compare(I, J)>0)
  43.             swap(dest, j, j-1);
  44.         }
  45.       }
  46.       return;
  47.     }
  48.     // Recursively sort halves of dest into src
  49.     int mid = (low + high) >>> 1;
  50.     mergeSort(dest, src, low, mid);
  51.     mergeSort(dest, src, mid, high);
  52.     I.set(src[mid-1]);
  53.     J.set(src[mid]);
  54.     // If list is already sorted, just copy from src to dest.  This is an
  55.     // optimization that results in faster sorts for nearly ordered lists.
  56.     if (comparator.compare(I, J) <= 0) {
  57.       System.arraycopy(src, low, dest, low, length);
  58.       return;
  59.     }
  60.     // Merge sorted halves (now in src) into dest
  61.     for (int i = low, p = low, q = mid; i < high; i++) {
  62.       if (q < high && p < mid) {
  63.         I.set(src[p]);
  64.         J.set(src[q]);
  65.       }
  66.       if (q>=high || p<mid && comparator.compare(I, J) <= 0)
  67.         dest[i] = src[p++];
  68.       else
  69.         dest[i] = src[q++];
  70.     }
  71.   }
  72.   private void swap(int x[], int a, int b) {
  73.     int t = x[a];
  74.     x[a] = x[b];
  75.     x[b] = t;
  76.   }
  77. }