Java Integer Comparison: More Than

I have an array of a million integers because I am experimenting with parallel quicksort. Sometimes I observe the following strange behavior:

To check if the array is sorted correctly, I entered the following code after sorting:

for(int j=0; j < array_parallel.length-1; ++j)
   if(array_parallel[j] > array_parallel[j+1])
    System.out.println("ERROR! NOT SORTED CORRECTLY!");

In some cases, I get the error output that it was not sorted correctly, and when I debug it, I find the following (an example, always different):

j = 1942 array_parallel [1942] = 6000; array_parallel [1943] = 6000;

(try to ignore numbers, not any specific value or range) Therefore, it is always in cases where the left value is equal to the correct value. Well, to compare more, this should return false, but I definitely get the output.

What the hell is wrong ??

I even cross-checked the array and it is sorted correctly. If I build a small array (about 100), it will also be fine. Am I missing something that my brain is fooling me with?

Edited 21:32 (UTC + 1):

private static int ANZAHL = 1000000;        // Größe des Arrays

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int array_single[] = new int[ANZAHL];
        int array_parallel[] = new int[ANZAHL];

        Speedmeasure sp_single = new Speedmeasure();
        Speedmeasure sp_parallel = new Speedmeasure();
        ArrayReader ar = null;

        try {
            ar = new ArrayReader(array_single, array_parallel);
        } catch (FileNotFoundException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (IOException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (ClassNotFoundException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        }

        if(ar == null) {
            System.err.println("Großes Problem. Lass es sein!");
            System.exit(-1);
        }
        else {

            for(int i=0; i < 5; ++i) {
                Quicksort_Single qs = new Quicksort_Single();
                sp_single.setStart(System.currentTimeMillis());

                qs.quicksort_start(array_single);
                sp_single.setStop(System.currentTimeMillis());

                //printArray(array);
                PrintSpeed(sp_single.getSpeed(), "Single");


                System.out.print("\nUnd jetzt treiben wir es parallel! \n\n");
                Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel));

                sp_parallel.setStart(System.currentTimeMillis());
                t1.start();

                try {
                    t1.join();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }

                sp_parallel.setStop(System.currentTimeMillis());

                //printArray(array_parallel);
                PrintSpeed(sp_parallel.getSpeed(),"Parallel");

                System.out.println("Speed up was: "+sp_parallel.calcSpeedup(sp_single.getSpeed(), sp_parallel.getSpeed()));
                System.out.println("******************************************");

                for(int j=0; j < array_single.length-1; ++j)
                    if(array_single[j] > array_single[j+1])
                        System.out.println("ERROR! NICHT SORTIERT KORREKT BEI SINGLE!");

                for(int j=0; j < array_parallel.length-1; ++j)
                    if(array_parallel[j] > array_parallel[j+1])
                        System.out.println("ERROR! NICHT SORTIERT KORREKT BEI PARALLEL!");



                ar.copyArray(array_single, array_parallel);
            }
        }
    }

I join a thread that initiates parallel sorting. The first thread, which simultaneously spawns up to 4 threads. I am not 100% sure that concurrency can be, as I see in the debugger, the array is sorted. I will add the output of two integers and look again.

Edited 05/23/12 16:46 UTC + 1

I changed everything to work with the new, and very simple, ForkJoinPool from JDK 1.7. Tested with integer arrays up to 10 mio integers and got interesting results: I tested it on Core2Duo (2010) MacBook Pro and Core-i5 (2011) Windows 7:

core2duo i5 , () * 2 → Core2duo 1,8 1,7 2 ; i5 3,2 8 () * 2

. , 1000 .