@Test public void testPartialRadixSortEmpty() { int[] data = new int[] {}; int[] test = Arrays.copyOf(data, data.length); Util.partialRadixSort(test); assertArrayEquals(data, test); }
public static void partialRadixSort(int[] data) { final int radix = 8; int shift = 16; int mask = 0xFF0000; int[] copy = new int[data.length]; int[] histogram = new int[(1 << radix) + 1]; while (shift < 32) { for (int i = 0; i < data.length; ++i) { ++histogram[((data[i] & mask) >>> shift) + 1]; } for (int i = 0; i < 1 << radix; ++i) { histogram[i + 1] += histogram[i]; } for (int i = 0; i < data.length; ++i) { copy[histogram[(data[i] & mask) >>> shift]++] = data[i]; } System.arraycopy(copy, 0, data, 0, data.length); shift += radix; mask <<= radix; Arrays.fill(histogram, 0); } }
Util { public static void partialRadixSort(int[] data) { final int radix = 8; int shift = 16; int mask = 0xFF0000; int[] copy = new int[data.length]; int[] histogram = new int[(1 << radix) + 1]; while (shift < 32) { for (int i = 0; i < data.length; ++i) { ++histogram[((data[i] & mask) >>> shift) + 1]; } for (int i = 0; i < 1 << radix; ++i) { histogram[i + 1] += histogram[i]; } for (int i = 0; i < data.length; ++i) { copy[histogram[(data[i] & mask) >>> shift]++] = data[i]; } System.arraycopy(copy, 0, data, 0, data.length); shift += radix; mask <<= radix; Arrays.fill(histogram, 0); } } }
Util { public static void partialRadixSort(int[] data) { final int radix = 8; int shift = 16; int mask = 0xFF0000; int[] copy = new int[data.length]; int[] histogram = new int[(1 << radix) + 1]; while (shift < 32) { for (int i = 0; i < data.length; ++i) { ++histogram[((data[i] & mask) >>> shift) + 1]; } for (int i = 0; i < 1 << radix; ++i) { histogram[i + 1] += histogram[i]; } for (int i = 0; i < data.length; ++i) { copy[histogram[(data[i] & mask) >>> shift]++] = data[i]; } System.arraycopy(copy, 0, data, 0, data.length); shift += radix; mask <<= radix; Arrays.fill(histogram, 0); } } private  Util(); }
Util { public static void partialRadixSort(int[] data) { final int radix = 8; int shift = 16; int mask = 0xFF0000; int[] copy = new int[data.length]; int[] histogram = new int[(1 << radix) + 1]; while (shift < 32) { for (int i = 0; i < data.length; ++i) { ++histogram[((data[i] & mask) >>> shift) + 1]; } for (int i = 0; i < 1 << radix; ++i) { histogram[i + 1] += histogram[i]; } for (int i = 0; i < data.length; ++i) { copy[histogram[(data[i] & mask) >>> shift]++] = data[i]; } System.arraycopy(copy, 0, data, 0, data.length); shift += radix; mask <<= radix; Arrays.fill(histogram, 0); } } private  Util(); static Container[] addOffset(Container source, char offsets); static int advanceUntil(char[] array, int pos, int length, char min); static int iterateUntil(char[] array, int pos, int length, int min); static void fillArrayAND(final char[] container, final long[] bitmap1,
      final long[] bitmap2); static void fillArrayANDNOT(final char[] container, final long[] bitmap1,
      final long[] bitmap2); static void fillArrayXOR(final char[] container, final long[] bitmap1,
      final long[] bitmap2); static void flipBitmapRange(long[] bitmap, int start, int end); @Deprecated static int cardinalityInBitmapWordRange(long[] bitmap, int start, int end); static int cardinalityInBitmapRange(long[] bitmap, int start, int end); static int maxLowBitAsInteger(); static void resetBitmapRange(long[] bitmap, int start, int end); static int intersectArrayIntoBitmap(long[] bitmap, char[] array, int length); static int select(long w, int j); static void setBitmapRange(long[] bitmap, int start, int end); @Deprecated static int setBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end); @Deprecated static int flipBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end); @Deprecated static int resetBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end); static int unsignedBinarySearch(final char[] array, final int begin, final int end,
      final char k); static int unsignedDifference(final char[] set1, final int length1, final char[] set2,
      final int length2, final char[] buffer); static int unsignedDifference(CharIterator set1, CharIterator set2,
                                       final char[] buffer); static int unsignedExclusiveUnion2by2(final char[] set1, final int length1,
      final char[] set2, final int length2, final char[] buffer); static int unsignedIntersect2by2(final char[] set1, final int length1, final char[] set2,
      final int length2, final char[] buffer); static boolean unsignedIntersects(char[] set1, int length1, char[] set2, int length2); static int unsignedLocalIntersect2by2Cardinality(final char[] set1, final int length1,
      final char[] set2, final int length2); static int unsignedUnion2by2(
          final char[] set1, final int offset1, final int length1,
          final char[] set2, final int offset2, final int length2,
          final char[] buffer); static long toUnsignedLong(int x); static void partialRadixSort(int[] data); }
Util { public static void partialRadixSort(int[] data) { final int radix = 8; int shift = 16; int mask = 0xFF0000; int[] copy = new int[data.length]; int[] histogram = new int[(1 << radix) + 1]; while (shift < 32) { for (int i = 0; i < data.length; ++i) { ++histogram[((data[i] & mask) >>> shift) + 1]; } for (int i = 0; i < 1 << radix; ++i) { histogram[i + 1] += histogram[i]; } for (int i = 0; i < data.length; ++i) { copy[histogram[(data[i] & mask) >>> shift]++] = data[i]; } System.arraycopy(copy, 0, data, 0, data.length); shift += radix; mask <<= radix; Arrays.fill(histogram, 0); } } private  Util(); static Container[] addOffset(Container source, char offsets); static int advanceUntil(char[] array, int pos, int length, char min); static int iterateUntil(char[] array, int pos, int length, int min); static void fillArrayAND(final char[] container, final long[] bitmap1,
      final long[] bitmap2); static void fillArrayANDNOT(final char[] container, final long[] bitmap1,
      final long[] bitmap2); static void fillArrayXOR(final char[] container, final long[] bitmap1,
      final long[] bitmap2); static void flipBitmapRange(long[] bitmap, int start, int end); @Deprecated static int cardinalityInBitmapWordRange(long[] bitmap, int start, int end); static int cardinalityInBitmapRange(long[] bitmap, int start, int end); static int maxLowBitAsInteger(); static void resetBitmapRange(long[] bitmap, int start, int end); static int intersectArrayIntoBitmap(long[] bitmap, char[] array, int length); static int select(long w, int j); static void setBitmapRange(long[] bitmap, int start, int end); @Deprecated static int setBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end); @Deprecated static int flipBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end); @Deprecated static int resetBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end); static int unsignedBinarySearch(final char[] array, final int begin, final int end,
      final char k); static int unsignedDifference(final char[] set1, final int length1, final char[] set2,
      final int length2, final char[] buffer); static int unsignedDifference(CharIterator set1, CharIterator set2,
                                       final char[] buffer); static int unsignedExclusiveUnion2by2(final char[] set1, final int length1,
      final char[] set2, final int length2, final char[] buffer); static int unsignedIntersect2by2(final char[] set1, final int length1, final char[] set2,
      final int length2, final char[] buffer); static boolean unsignedIntersects(char[] set1, int length1, char[] set2, int length2); static int unsignedLocalIntersect2by2Cardinality(final char[] set1, final int length1,
      final char[] set2, final int length2); static int unsignedUnion2by2(
          final char[] set1, final int offset1, final int length1,
          final char[] set2, final int offset2, final int length2,
          final char[] buffer); static long toUnsignedLong(int x); static void partialRadixSort(int[] data); static final boolean USE_HYBRID_BINSEARCH; }