321803 - Array.sort(comparefunction), returns desordened when compare function returns 0 in array multidimensional

Status: RESOLVED DUPLICATE of bug 224128

(Core :: JavaScript Engine, defect)

Description

[Felipe]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.12) Gecko/20050915
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.12) Gecko/20050915

var myarray = [0,1,2,3,4]
var myarray2 = ["teste0","teste1","teste2","teste3","teste4"]
var myarray3 = ["teste00","teste01","teste02","teste03","teste04"]

myarray[0] = myarray2;
myarray[1] = myarray3;
myarray[2] = myarray2;
myarray[3] = myarray3;
myarray[4] = myarray3;

myarray.sort(CompFunc);

function CompFunc(a,b){

return 0;

}

###
### When CompFunc returns 0, the mozilla navigator/ firefox, don't sort
### myarray correctly. But the IE returns right.
### This problem it occurs in arrays multidimensionals.

Reproducible: Always

Steps to Reproduce:
1.Create a multidimension array
2.Sort this array by a param of this array
3.the returns of this sort is incorrect when the functioncompare, returns 0.

Actual Results:  
The array was disordered.

Expected Results:  
Sort the array multdimension:
[0] -> a
[0] -> b
[0] -> c
[1] -> a
[1] -> b
[1] -> c
and not
[0] -> b
[0] -> a
[0] -> c
[1] -> c
[1] -> a
[1] -> b

Error in Mozilla Navigator e Firefox.

Comment 1

[Thomas Andrews]

It's not clear what you expect this code to do, but the comparison function passed to sort should only return zero if you want the two values, a and b, to be considered equal in the sort order.  Since the comparison function is always returning zero, that means that any result of the sort is allowed.

It's not clear what you expect, but the multidimensional nature of the array is irrelevant.  The 'sort' method treats the array as a single array, and it sorts the single array.

Also, the section on 'what you expect' is completely useless - it bears no relation to the example input - what are 'a', 'b', and 'c'?

Comment 2

[Thomas Andrews]

I also was not able to reproduce any different behavior in IE.

See:

  http://www.thomasoandrews.com/examples/mozilla/321803/

for an extension of your code, printing the array after the sort.

See:

  http://www.thomasoandrews.com/examples/mozilla/321803/1d.html

for a one-dimensional example.

Comment 3

[Erik Fabert]

If I understand the reporter correctly this bug report is about sort() not being a stable sort: elements that compare equal may switch positions. Strictly speaking this is not a bug because it's allowed by the ECMA specification but nevertheless the behaviour may change in the future, see bug 224128.

Comment 4

[Felipe]

well, look this.
this is my script:
var myarray = new Array();
var myarray2 = new Array();
var myarray3 = new Array();
var myarray4 = new Array();
var myarray5 = new Array();
var myarray6 = new Array();

myarray2["name"] = "nameA";
myarray2["fone"] = "foneA";

myarray3["name"] = "nameB";
myarray3["fone"] = "foneB";

myarray4["name"] = "nameC";
myarray4["fone"] = "foneC";

myarray5["name"] = "nameD";
myarray5["fone"] = "foneD";

myarray6["name"] = "nameD";
myarray6["fone"] = "foneD";

myarray[0] = myarray5;
myarray[1] = myarray3;
myarray[2] = myarray4;
myarray[3] = myarray2;
myarray[4] = myarray6;

/*
in this moment myarray is :

[0] => name => nameD
[0] => fone => foneD

[1] => name => nameB
[1] => fone => foneB

[2] => name => nameC
[2] => fone => foneC

[3] => name => nameA
[3] => fone => foneA

[4] => name => nameD
[4] => fone => foneD

*/

myarray.sort(compfunc);
myarray.sort(compfunc2);

function compfunc(a,b){
	if(a.name > b.name){
		return 1;
	}
	if(a.name < b.name){
		return -1;
	}
	return 0;
}

function compfunc2(a,b){
	if(a.name == b.name){
		if(a.fone > b.fone){
			return 1;
		}
		if(a.fone < b.fone){
			return -1;
		}
		return 0;
	}else{
		return 0;
	}
}

/*
my result in Mozilla is:

[0] = > name => "nameC"
[0] = > fone => "foneC"
[1] = > name => "nameB"
[1] = > fone => "foneB"
[2] = > name => "nameD"
[2] = > fone => "foneD"
[3] = > name => "nameA"
[3] = > fone => "foneA"
[4] = > name => "nameD"
[4] = > fone => "foneD"

my result in IE:

[0] = > name => "nameA"
[0] = > fone => "foneA"
[1] = > name => "nameB"
[1] = > fone => "foneB"
[2] = > name => "nameC"
[2] = > fone => "foneC"
[3] = > name => "nameD"
[3] = > fone => "foneD"
[4] = > name => "nameD"
[4] = > fone => "foneD"


I need the result of the IE in mozilla too.
*/

Comment 5

[Andrew Schultz]

==> JS engine

Comment 6

[Brendan Eich [:brendan]]

Attachment: cleaned up testcase, with print statements showing intermediate states

This bug is a dup.  IE uses a stable sort.  ECMA does not require it, so your code is not portable.  If you want stability and portability, fix compfunc2 to return compfunc(a, b) if a.name and b.name are not equal:

function compfunc2(a,b){
        print('compfunc2', ue(a), ue(b));
        if(a.name == b.name){
                if(a.fone > b.fone){
                        return 1;
                }
                if(a.fone < b.fone){
                        return -1;
                }
                return 0;
        }
        return compfunc(a, b);
}

/be

Comment 7

[Brendan Eich [:brendan]]

*** This bug has been marked as a duplicate of 224128 ***