How does the sort() work in javascript?

Question

var numArray = [4,2,5,3];
numArray.sort(function(a,b){
  console.log("a:" + a + ", b:" + b);
  return a-b;
});

The three possible return numbers are: <0 (less than 0), 0, or >0 (greater than 0):

 Less than 0: Sort "a" to be a lower index than "b"
 Zero: "a" and "b" should be considered equal, and no sorting performed.
 Greater than 0: Sort "b" to be a lower index than "a".

I am getting like this on console

    a:4, b:2
    a:4, b:5
    a:5, b:3
    a:2, b:3
    a:4, b:3
    [2, 3, 4, 5]

May I know how the values of a and b are getting changed as seen above?

In the first step a=4 and b=2. In this case it will swap. then the array becomes [2,4,5,3];

In the second step a=4 and b=5. In this case the items remains same. then the array becomes [2,4,5,3];

In the third step a=5 and b=3. In this case it will swap. then the array becomes [2,4,3,5];

Until this step it is okay. But after that how the value of a and b becomes 2 and 3 > respectively instead of 2 and 4.

Anyone can help me?

Thanks in advance

This probably depends on the browser. Which browser are you using? — Mark Byers
– Mark Byers, Commented Jun 29, 2012 at 6:09
Array sort uses whatever algorithm it wants. You are expecting a simple bubble sort, but it doesn't have to do that. Your function is used only as the basis of comparison of values. — RobG
– RobG, Commented Jun 29, 2012 at 6:10
Mark: I have checked this in 2 browsers firefox and chrome. The result is same — Sreehari
– Sreehari, Commented Jun 29, 2012 at 6:14
RobG: If it is comparison of value after third step how the value of and b changes to 2 and 3 instead of 2 and 4. — Sreehari
– Sreehari, Commented Jun 29, 2012 at 6:23
Because it isn't doing a simple bubble sort. Perhaps someone who knows more than me about sort algorithms (pretty much anyone!) can identify which one is being used. — RobG
– RobG, Commented Jun 29, 2012 at 6:38

Mark Byers · Accepted Answer · 2012-06-29 06:49:40Z

2

There is no guarantee that the sort method uses a simple compare and swap algorithm.

More likely your browser uses something like merge sort, but the specific algorithm will depend on the browser and version.

Since Firefox is open source you can see how sort is implemented by checking the source code. It uses a merge sort.

edited Jun 29, 2012 at 6:49

answered Jun 29, 2012 at 6:11

Mark Byers

843k202 gold badges1.6k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mark Byers Over a year ago

@Joey: I wouldn't say that merging is simple swapping. Obviously the result is that the data is swapped at the end, but the steps to get there can be more complicated than just simply swapping elements in-place.

Joey Over a year ago

Hm, you're right. Conceptually I just quickly thought about Quicksort, Heapsort and the n² ones but somehow ignored Mergesort.

Collectives™ on Stack Overflow

How does the sort() work in javascript?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related