Skip to content

Instantly share code, notes, and snippets.

@und3f
Created November 29, 2021 09:40
Show Gist options
  • Save und3f/d8418017b832f7fe2da65140a0fc1af2 to your computer and use it in GitHub Desktop.
Save und3f/d8418017b832f7fe2da65140a0fc1af2 to your computer and use it in GitHub Desktop.
Sort million 32-bit integers
import java.util.Random;
import java.util.Arrays;
import java.time.*;
import java.time.temporal.*;
public class MillionDWords {
final static int million = 1_000_000;
final static int runs = 100;
public static void main(String []argc) {
int[] numbers = new Random().ints(million, Integer.MIN_VALUE, Integer.MAX_VALUE).toArray();
int[] numbers2 = Arrays.copyOf(numbers, numbers.length);
LocalTime initTime = LocalTime.now();
Arrays.sort(numbers);
System.out.printf("Arrays.sort() sorted in %10d ns\n",
ChronoUnit.NANOS.between(initTime, LocalTime.now()));
// System.out.println(Arrays.toString(numbers));
initTime = LocalTime.now();
LSDSort(numbers2);
System.out.printf("LSD() sorted in %10d ns\n",
ChronoUnit.NANOS.between(initTime, LocalTime.now()));
// System.out.println(Arrays.toString(numbers2));
System.out.printf("Arrays are equals: %b\n",
Arrays.equals(numbers, numbers2));
}
private static int byteAt(int number, int position) {
return ((number ^ (1 << (7+8+8+8))) >>> (8 * (3-position))) & 0xFF;
}
private static void LSDSort(int[] a) {
final int N = a.length;
final int R = 1<<8;
final int W = 4;
int[] aux = new int[N];
for (int d = W-1; d >= 0; d--) {
int[] count = new int[R+1];
for (int i = 0; i < N; i++)
count[byteAt(a[i], d) + 1]++;
for (int r = 0; r < R; r++)
count[r+1] += count[r];
for (int i = 0; i < N; i++)
aux[count[byteAt(a[i], d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = aux[i];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment