[eut][classlib][luni] - Arrays.sort(T[] a, Comparator<? super T> c) is not stable

• Key: HARMONY-6076
• Type: Bug
• Status: Closed
• Resolution: Fixed
• Priority: Major
• Assignee: Sean Qiu
• Reporter: Regis Xu
• Component/s: Classlib
• Affects Version/s: 5.0M8
• Fix Version/s: 5.0M9

Description

spec says "This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort."
but Harmony's implementation is not, which cause eut failure in org.eclipse.jdt.core.tests.compiler.test074 - 1.3

see the following test:

public class TestArrays {
    public static void main(String[] args) {
        Element[] array = new Element[11];
        array[0] = new Element(122);
        array[1] = new Element(146);
        array[2] = new Element(178);
        array[3] = new Element(208);
        array[4] = new Element(117);
        array[5] = new Element(146);
        array[6] = new Element(173);
        array[7] = new Element(203);
        array[8] = new Element(56);
        array[9] = new Element(82);
        array[10] = new Element(96);
        for (int i = 0; i < array.length; i++) {
            System.out.println("Element value is " + array[i].getValue()
                    + " index is " + array[i].getIndex());
        }

        Arrays.sort(array, new ElementComparator());

        for (int i = 0; i < array.length; i++) {
            System.out.println("Element value is " + array[i].getValue()
                    + " index is " + array[i].getIndex());
        }
    }

    public static class Element {
        private int value;

        private int index;

        public int getIndex() {
            return index;
        }

        private static int count = 0;

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Element(int value) {
            this.value = value;
            index = count++;
        }
    }

    public static class ElementComparator implements Comparator {

        public int compare(Object arg0, Object arg1) {
            return ((Element) arg0).getValue() - ((Element) arg1).getValue();
        }

    }
}

notice array[1] and array[5] has the same value, the indexes are 1 and 5 corresponding, after a stable sort, element has index 1 should be ahead of element has index 5

output of RI:

=========before sort=============
Element value is 122 index is 0
Element value is 146 index is 1
Element value is 178 index is 2
Element value is 208 index is 3
Element value is 117 index is 4
Element value is 146 index is 5
Element value is 173 index is 6
Element value is 203 index is 7
Element value is 56 index is 8
Element value is 82 index is 9
Element value is 96 index is 10

=========after sort=============
Element value is 56 index is 8
Element value is 82 index is 9
Element value is 96 index is 10
Element value is 117 index is 4
Element value is 122 index is 0
Element value is 146 index is 1
Element value is 146 index is 5
Element value is 173 index is 6
Element value is 178 index is 2
Element value is 203 index is 7
Element value is 208 index is 3

output of Harmony:

=========before sort=============
Element value is 122 index is 0
Element value is 146 index is 1
Element value is 178 index is 2
Element value is 208 index is 3
Element value is 117 index is 4
Element value is 146 index is 5
Element value is 173 index is 6
Element value is 203 index is 7
Element value is 56 index is 8
Element value is 82 index is 9
Element value is 96 index is 10

=========after sort=============
Element value is 56 index is 8
Element value is 82 index is 9
Element value is 96 index is 10
Element value is 117 index is 4
Element value is 122 index is 0
Element value is 146 index is 5
Element value is 146 index is 1
Element value is 173 index is 6
Element value is 178 index is 2
Element value is 203 index is 7
Element value is 208 index is 3

notice that in Harmony index 1 and 5 is out of order after sort

Comments

[Sean Qiu]

The incorrect patch is reverted at r742850.
Could you please verify it?

Thank you very much.

[Regis Xu]

add regression test

[Sean Qiu]

Thanks for your testcase.
It is applied at r743233.
Please verify if it works as you expected.

[Regis Xu]

Verified. Thanks Sean.