How does Array.sort() work?

I have noticed that the sorting occurs by converting each element to string and comparing the unicode numeric characters for that symbol.

MDN also has many more advanced details than that. I wanted to compare numbers so the solution on the web uses:

[...arr].sort((a,b)=>b-a))

The shallow copy is so we can keep the original array.

I can’t find though, how is the result of that operation influences the sorting. I guess something like this happens:

  1. b-a larger than 0 then test with next element
    a. when it changes sign place before that element
  2. b-a less than 0 put it first
  3. If 0 place there

But as I said before the sorting functions aren’t the easiest to set, I think. But do you think that is more or less how the function is used by Array.sort(fn) ?

You are mentioning MDN article.

In description section of it, there is explanation how this one works. Compare it to your own conclusions.

I am not sure what else can be added to such explanation.

This article at the very start refers to in-place algorithm so you can read about that. In-place algorithm - Wikipedia

Also you can go straight to the specs: ECMAScript® 2023 Language Specification

But that’s not the easiest reading

UPDATE. Almost forgot - if you want learn more about sorting problems and get some practice at the same time, you can go to the code prep course of curriculum, there are bunch of challenges in algorithms section: some of them about sorting.

1 Like

Yes, but they do not describe exactly how this is done. For example, when it sorts “b”, is it “b” always the same element and it goes trying “a” for each element in the array ? You could think that there are smarter ways to do it, or just different ones. And then moves to element indexOf(b)+1 and repeats?

Appreciate all the links!

PD I read the algorithm from the specs, very interesting. It is actually like that, amazing to see how clear they can explain it.

I am not sure if there is one exact answer about how exactly this is done. Take a look at this discussion for example:
https://stackoverflow.com/questions/57763205/what-is-array-prototype-sort-time-complexity

There isn’t in the spec. They dont even mention iteration.
That discusses the time though? @admit8490

Found some here though algorithm - Javascript Array.sort implementation? - Stack Overflow

I presume this is quite complex so I’ll stop there lol. But it is interesting.

Thanks.

Well, I’ll stop here too. Maybe it is not super complex, but I am not sure I need to spend more time for sorting details right now.

Do you know about all those sorting algorithms? It’d be nice to discuss it. Just the logic maybe.

There is QuickSort, MergeSort etc. For the web is literally seeing how it was implemented as well.

I implemented bubble sort, merge sort and selection sort.

I am for some reason stuck in insertion sort. Maybe just because I was kinda tired when dealing with that.

And I am stuck with quick sort because there is some recursion, recursion is always not really easy.

bubble sort seems to be most simple one to understand and implement. But it is not the very efficient algo.

1 Like