Discussion on: Array sort

View post

This effectively makes any custom sort function a reducer by default and thus any sorting algorithm relying on an outer loop only needs to provide the contents of that outer loop.

I found the implementation of the sort(collection, sortFn) function slightly confusing, in the sense that it expects a sortFn that is forced to rely on an outer loop. Consequently, I'm not sure if the following statement from the beginning is correct:

"We will aim to match the sort functions signature but not the compareFunction functions signature since we want to allow people to use any algorithm and not just a simple 1, -1, and 0 comparitor."

What if your custom sort function doesn't work with an outer loop? For example, when you want to use Quick sort or a custom merge sort implementation?

That doesn't seem to be possible, except if you rely on the 4th reduce argument (previous, current, index, collection) => { ...... } to work on the collection directly. But then the outer looping behavior will still persist and require some ugly hacks work around.

James Robb • Apr 25 '20

The default Javascript sort is just a reducer effectively though. It loops each item gives you the current and next and uses the return value to denote the next position of the current item, swaps and setups the next iteration. I suppose I could just write sort like this:

function sort(collection, sortFn) {
  if(sortFn && typeof sortFn === "function") {
    return sortFn([...collection]);
  }

  return mergeSort([...collection]);
}

Now the default is the same but you can pass in quick sort or any other algorithm you like.

I initially used a reducer because during my creating of this article, I tested with non-recursive algorithms and so things like bubble sort, etc were easy to implement and seemed to work well with this model but you have a point, recursive algorithms don't seem to play so well with this. Perhaps I will change the article to reflect the code I added in this comment instead. I'll think about it after some more testing.

Thor Galle • Apr 25 '20

Yup, that was my point! And that would be the full solution, but then you miss your abstraction of the outer loop.

I mean, it could be OK to keep the code it as-is, but then the "any algorithm" statement in the beginning is a bit misleading. Replacing with something like "any sorting algorithm with an outer loop" seems more correct. I'm not familiar with functional implementations of sorting algorithms, I would have to look at that.

James Robb • Apr 25 '20

Yeah, I will update the article through next week and rewrite some of the tests and code since I can actually use this chance to link back to the other articles in the series on different sorting algorithms anyway and so it keeps things tidy and linked with one another narratively anyway.