Re: [Fwd: java/1895: Libjava: Arrays.sort doesn't work]

[Mark Benvenuto]

Bryce McKinlay wrote:

> Here's a bug report we received through the GCC bug tracking system.
> It looks like the qsort implementation in java.util.Arrays is broken
> for large arrays ;-(
>
> Does anyone know qsort well enough to take a look?

Fixed. See Patch. The bugs was a problem that depends on the fact that our
qsort implmentation does not happen arrays of length 7 very well. After
recieving seven numbers from a first qsort, the qsort is suppose to divide
and conquer the seven numbers. The problem is since the 7 numbers are not run
through a proper divide (or med3) algorithm, the first number is picked (a
worst case qsort scenario) _incorrectly_ and the next six numbers are
processed by ultimately an insert sort. In a proper median algorithm, if the
the first number was to be picked it would be the lowest one but in this case
it could be any value. The fix is to handle the array size = 7 by adding an =
sign to either the insertion sort routine or if statement wrapping the med3
calls. Now back to HW :(

int[] A = {61, 95, 198, 123, 167, 55, 88, 41, 177, 1, 146};

Mark

=======================================

--- Arrays.java.orig Wed Feb  7 01:50:29 2001
+++ Arrays.java Wed Feb  7 01:57:04 2001
@@ -1101,7 +1101,7 @@
   private static void qsort(byte[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
@@ -1219,7 +1219,7 @@
   private static void qsort(char[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
@@ -1338,7 +1338,7 @@
   private static void qsort(double[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
@@ -1457,7 +1457,7 @@
   private static void qsort(float[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
@@ -1575,7 +1575,7 @@
   private static void qsort(int[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
@@ -1693,7 +1693,7 @@
   private static void qsort(long[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
@@ -1811,7 +1811,7 @@
   private static void qsort(short[]a, int start, int n)
   {
     // use an insertion sort on small arrays
-    if (n < 7)
+    if (n <= 7)
       {
  for (int i = start + 1; i < start + n; i++)
    for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)