Mubashir Hassan

Posted on Dec 13, 2022

Array.sort() in JavaScript - I was asked about this in an interview

#javascript #arrays #webdev #programming

I was in an interview and I was given an array of strings.

const arr = [
  "karachi",
  "lahore",
  "kolachi",
  "islamabad"
]

He asked me to sort it in alphabatical order.

I tried:

arr.sort((a, b) => {
  return a < b;
});

He said it will work for numbers (actually it won't) but does not work for strings.

Then I tried

arr.sort((a, b) => {
  return a.charAt(0) < b.charAt(0);
});

He said it will work for just the first characters (actually it won't), then how karachi and kolachi starting with k will be sorted?

I was blank.

He said what are a and b?

I said a is the current element (the element at the index of current iteration) and b is the next element (the element at the current iteration + 1 index).

👉 But actually, it is the opposite. a is the next element and b is the current element.

Then he asked, does the sort modify the original array or returns a new array.

Honestly, most of the time I am working with .map(), .filter(), .some(), and .every(). So I knew the behaviour of these methods but I don't remember when was the last time I used .sort().

I said, it does not modify the original array, rather returns a new array like .map().

👉 But it is the opposite. .sort() modifies the original array and returns the reference to the original array, which is now sorted.

How does actually `.sort()` work?

Array.sort() accepts a an optional compare function as an argument.

If we do not provide any compare function, the sort method converts all the non-undefined elements to string, and then compare their sequences of UTF-16 code units values.

What does "compare their sequences of UTF-16 code units values" means?
To put it simple, let's say we write character a which is encoded as UTF-16 in JavaScript. In decimal it's value will be 97. For b it will be 98. i.e.
A = 65
B = 66
C = 67
and so on.
I expect you know the ASCII table.

So basically the array of strings will automatically be sorted by .sort() method correctly without passing any compare function.

👉 In case of numbers, the behaviour is same;

const arr = [1, 30, 4, 21, 100000];
arr.sort();
console.log(arr);
// expected output: [1, 100000, 21, 30, 4]

Because each number is first converted into string, and then compared with respect to their UTF-16 code units values.

But If we provide a compare function to sort based on numbers:

const arr = [1, 5, 3, 10, 7]
arr.sort((nextValue, prevValue) => {
  // if returnValue > 0, move nextValue after the prevValue
  // if returnValue < 0, move the nextValue before the prevValue
  // if returnValue === 0, keep the original order, do not move any value
  return nextValue - prevValue;
});

So, the sort method can be thought of like this:

function compareFunction(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  a must be equal to b
  return 0;
}

I hope this will make the things a bit clear about Array.sort()

That's it for this post. Write your thoughts in the comments below!

Top comments (8)

Matija Novosel • Dec 15 '22 • Edited

The interviewer could have been more precise with the question because there are native ways of sorting strings, that being the localeCompare method:

const x = ["z", "aa", "ab", "Yo"];
x.sort((a, b) => a.localeCompare(b)); // ["aa", "ab", "Yo", "z"]

Although, that is beside the point it seems because he was just trying to nitpick.

David Morrow • Dec 17 '22

if you are dealing with strings, this is the correct way to sort.

FJones • Dec 14 '22

Now, granted, the interviewer seems to have had a rather light grasp of the sort function themselves, but your attempts weren't ideal either.

The compare function shouldn't return the result of a comparison operator (except for the yet-to-be-standardized spaceship operator <=>), as it specifically ought to return {-1,0,1}. It works with comparison operators because of a lot of fallbacks and a lot of developers making that mistake, but that doesn't make it a good choice.

The same applies to the number example using -, fwiw. While it at least gets the correct sign for the return value, it still returns values outside of the defined set.

teamradhq • Dec 15 '22

The compare function should return a negative, zero or positive value.

From the documentation:

If compareFn is supplied, all non-undefined array elements are sorted according to the return value of the compare function (all undefined elements are sorted to the end of the array, with no call to compareFn).

`compareFn(a, b)`return value	sort order
`> 0`	sort `a` after `b`
`< 0`	sort `a` before `b`
`=== 0`	keep original order of `a` and `b`

So, the compare function has the following form:

function compareFn(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

The values -1 and +1 in the example are placeholder for any negative and positive values. So the example works not because of mistakes or fallbacks, but because the implementation meets the requirements for a compare function:

// Returns < 0 | === 0 | > 0
const sort = (next: number, prev: number): number => next - prev;

This is also a correct implementation for a spaceship operator, which should return { -0, 0, +0} to indicate { <, =, > } comparison respectively. A set of { -0, 0, +0 }, { -1, 0, +1 } and { -1234, 0, +1234 } are all equally valid implementations for the result of a spaceship comparison.

I'd argue that the bad choice here would be increasing complexity by adding redundancy:

function sort(next: number, previous: number): -1 | 0 | 1 {
  const result = next - previous;

  if (result < 0) {
    return -1;
  }

  if (result > 0) {
    return 1;
  }

  return 0;
}

I think that this pattern is a mistake because it's functionally equivalent, and equally as valid as:

const sort = (next: number, previous: number) => next = previous;

Explicitly returning one of three primitive values really makes sense for arbitrary sorting conditions. Say, if you wanted to sort a collection of records based on something less trivial. For example, imagine we have a collection of models with types { department, employee, resource }:

function arbitrarySort(next: Model, prev: Model): -1 | 0 | 1 {
  if (next.type === 'department') {
    return -1;
  }

  if (next.type !== 'employee') {
    return prev.type == 'department' ? 1 : -1;
  }

  return 0;
}

This comparison function sorts the collection by type, placing any department at the top of the list, any employee at the bottom, and resources in the middle.

Obviously, this is a super contrived example and I would probably recommend a different pattern for this kind of operation because it doesn't make much conceptual sense here.

A more concrete example might be a collection of survey responses to a { yes, no, unanswered } question with values resolving to { true, false, null } respectively.

This will sort the questions in the order yes, no, unanswered:

function sortByAnswer(next: Quiz, prev: Quiz) {  
  if (next.answer === null) {  
    return 1;  
  }  

  if (next.answer === true) {  
    return -1;  
  }  

  if (next.answer === false && prev.answer === null) {  
    return -1;  
  }  

  return 0;  
}

The point I'm trying to make here is that we should only reach for this pattern if comparison is non-trivial. That is, the result of our comparison operation doesn't yield a numeric or character value:

if (less) {
  return -1;
}

if (more) {
  return 1;
}

return 0;

We shouldn't consider this comparison function to be erroneous in any way:

(a, b) => a - b;

MoshiKoi • Dec 14 '22

Small correction:

it specifically ought to return {-1,0,1} ... The same applies to the number example using -, fwiw. While it at least gets the correct sign for the return value, it still returns values outside of the defined set.

It actually works as long as the sign (and of course zero for equality) are correct; it does not specifically have to be {-1, 0, 1}

If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative Number if x < y, a positive Number if x > y, or a zero otherwise.

source