Array.prototype.sort Temporarily Duplicating Content?

Question

I recently wanted to walk somebody through how Array.prototype.sort uses a custom method to compare two values at any given time, and decide whether they should be swapped or left alone. I decided to log the array during each comparison so the result of the previous comparison could be seen. When I logged the array, I noticed something rather odd about the state of the array at certain moments.

Assuming the following:

var num = [ 2, 1, 8, 5, 3 ];

num.sort( comparator );

function comparator ( a, b ) {
    console.log( num ); // Current state of num
    return a - b; // Order values numerically
}

This is the output:

[ 2, 1, 8, 5, 3 ] // Comparing 2 and 1
[ 1, 2, 8, 5, 3 ] // Comparing 2 and 8
[ 1, 2, 8, 5, 3 ] // Comparing 8 and 5
[ 1, 2, 8, 8, 3 ] // Comparing 2 and 5
[ 1, 2, 5, 8, 3 ] // Comparing 8 and 3
[ 1, 2, 5, 8, 8 ] // Comparing 5 and 3
[ 1, 2, 5, 5, 8 ] // Comparing 2 and 3

The array is sorted properly ([ 1, 2, 3, 5, 8 ]) but I am still left scratching my head at some of the passes on the collection itself.

How is it that 8 appears twice on iteration 4, replacing 5 temporarily. And again, 8 appears twice two iterations later replacing 3 temporarily. Lastly, 5 appears twice, temporarily replacing 3 in the last iteration.

Note that the above code was ran in Chrome.

Answer 1

Interesting, but not too surprising.

It appears to be using a simple insertion-sort algorithm in this instance.

Something along the lines of:

• Get item [1]
• Shift every item below it up one until you find an item that's lower, then put above this item
• Get item [2]
• Shift every item below it up one until you find an item that's lower, then put it above this item
• Get item [3]
• (cont)

When describing the bubble sort algorithm, you usually imagine each element being swapped along the array until it finds its place. But it's more efficient to store the item into a temporary variable than to swap it.