FULL PRODUCT VERSION :
java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Ubuntu 16.04 x64 - Linux james-ubuntu 4.4.0-66-generic #87-Ubuntu SMP Fri Mar 3 15:29:05 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

Microsoft Windows [Version 10.0.14393]


A DESCRIPTION OF THE PROBLEM :
After calling Collections.sort the collection may contain different elements. This occurs if the Comparator used throws an exception while TimSort is performing a merge (an example stack is output by the example code).

This cause the merge to fail and results in elements in the collection being duplicated while others are lost. The length of the collection is correctly maintained.

This was found while investigating a test failure in Jython. More details can be found on the ticket http://bugs.jython.org/issue2399

REGRESSION. Last worked in version 7u80

ADDITIONAL REGRESSION INFORMATION:
java version "1.7.0_80"
Java(TM) SE Runtime Environment (build 1.7.0_80-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.80-b11, mixed mode)


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the example code provided

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The example code should produce the following output:

After sort distinct elements: 128

ACTUAL -
The example code produces the following output:

After sort distinct elements: 126

Indicating elements have been lost while others are duplicated.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

public class TestSort {

    private static class Complains {
        public final int i;
        
        public Complains(int i) {
            this.i = i;
        }

        @Override
        public String toString() {
            return "Complains(" + i + ")";
        }
    }

    private static class ComplainsComparator implements Comparator<Complains> {
        @Override
        public int compare(Complains o1, Complains o2) {
            // Values chosen to fail when TimSort is in the mergeLo function
            if (o1.i == 30 && o2.i == 43) {
                System.out.println("Throwing exception");
                throw new RuntimeException();
            }
            return o1.i < o2.i ? -1 : 1;
        }
    }

    public static void main(String[] args) {
        List<Complains> complainsList= new ArrayList<>(128);

        int[] nums = new int[]{50, 84, 104, 51, 75, 15, 66, 43, 17, 70, 74, 60, 113, 91, 71, 56, 76, 24, 123, 30, 28, 69, 96, 58, 109, 36, 32, 57, 79, 46, 67, 99, 72, 93, 101, 63, 126, 48, 65, 10, 78, 12, 119, 115, 53, 11, 33, 87, 114, 118, 44, 3, 100, 19, 27, 122, 121, 39, 25, 22, 2, 54, 16, 52, 124, 61, 13, 88, 0, 47, 40, 116, 98, 81, 6, 102, 35, 31, 73, 105, 77, 5, 23, 20, 7, 117, 107, 106, 42, 1, 21, 29, 8, 82, 95, 111, 14, 26, 85, 108, 97, 45, 80, 38, 64, 41, 9, 59, 62, 127, 110, 125, 90, 92, 120, 34, 83, 4, 49, 103, 68, 94, 55, 112, 18, 37, 86, 89};

        for (int i : nums) {
            complainsList.add(new Complains(i));
        }

        System.out.println("Before sort:" + complainsList);
        System.out.println("Before sort list size: " + complainsList.size());
        System.out.println("Before sort distinct elements: " + new HashSet<>(complainsList).size());

        try {
            System.out.println("Do sort");
            Collections.sort(complainsList, new ComplainsComparator());
        }
        catch (Exception e) {
            e.printStackTrace();
        }

        System.out.println("After sort" + complainsList);
        System.out.println("After sort list size: " + complainsList.size());
        System.out.println("After sort distinct elements: " + new HashSet<>(complainsList).size());
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
You can disable TimSort by setting the system property -Djava.util.Arrays.useLegacyMergeSort=true