Array sort

Sorting collections of data is beneficial in many scenarios and can be done in many ways. We have seen some of the more popular sorting algorithms in my algorithms article series, namely: Bubble sort, Selection sort, Insertion sort, Quick sort and Merge sort.

By default in most languages, there is some form of default implementation of a sorting function available. For example if we want to sort a collection in ascending order using JavaScript we can use collection.sort(), with PHP we could use sort(collection) and in Python we could use sorted(collection).

We will be implementing our custom sort function in JavaScript for this post and so here is a fuller example of how the default implementation works:

const collection = [3, 1, 2];
const sorted = collection.sort(); // [1, 2, 3]

Simple right? Different JavaScript engines use different algorithms for the sort function but overall they produce the same result. Now, to our custom implementation!

Tests

describe('sort', () => {
  it('should sort with default implementation and no sortFn requirement', () => {
    const collection = [3, 1, 2];
    const actual = sort(collection);
    const result = [1, 2, 3];
    expect(actual).toStrictEqual(result);
  });

  it('should apply the sortFn correctly', () => {
    /**
     * @function sortFn
     * @description Example of using selection sort as the sortFn param
     * @param {Array} previous - The last element for comparison
     * @param {*} current - The current element for comparison
     * @param {Number} index - The index of the current item
     * @returns {Array} The array for the next iteration of the sortFn to receive
     */
    function sortFn(previous, current, index, array) {
      let low = index;

      for (let inner = index + 1; inner < array.length; inner++) {
        if (array[inner] < array[low]) {
          low = inner;
        }
      }

      if (array[index] > array[low]) {
        const tmp = array[index];
        array[index] = array[low];
        array[low] = tmp;
      }

      return array;
    };

    const collection = [3, 1, 2];
    const actual = sort(collection, sortFn);
    const result = [1, 2, 3];
    expect(actual).toStrictEqual(result);
  });
});

Here we see tests for default sorting which will do the same as most other implementations and be sorted ascending by default when a custom sortFn function is not provided.

If a custom sortFn function is provided, we will run it instead of the default, in our case we are using Selection sort as the algorithm in the custom sortFn function test.

Implementation

The native sort function has the following signature:

arr.sort(function compareFunction(currentItem, nextItem) {
  if (currentItem is less than nextItem by some ordering criterion) {
    return -1;
  }
  if (currentItem is greater than nextItem by some ordering criterion) {
    return 1;
  }

  // currentItem must be equal to nextItem
  return 0;
});

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. With that said, here is our implementation:

/**
 * @function merge
 * @description Merges two arrays and sorts them as it does
 * @param {Array} left
 * @param {Array} right
 * @returns {Array} The sorted merge of the left and right arrays
 */
function merge(left, right) {
  const result = [];

  while(left.length || right.length) {
    if(left.length && right.length) {
      result.push(left[0] < right[0] ? left.shift() : right.shift());
    } else {
      result.push(left.length ? left.shift() : right.shift());
    }
  }

  return result;
}

/**
 * @function mergeSort
 * @description A merge sort implementation
 * @param {Array} collection - The collection to sort
 * @returns {Array} The sorted collection
 */
function mergeSort(collection) {
  if(collection.length <= 1) return collection;

  const middle = collection.length / 2 ;
  const left = collection.slice(0, middle);
  const right = collection.slice(middle, collection.length);

  return merge(
    mergeSort(left),
    mergeSort(right)
  );
}

/**
 * @function sort
 * @description Sorts a collection by either applying a given sorting function. If none is provided, a merge sort implementation will be used to sort the collection in ascending order.
 * @param {Array} collection - The collection to be sorted
 * @param {Function} [sortFn] - An optional custom sorting function which will receive the current and next elements per iteration of the collection
 * @returns {Array} The sorted collection
 */
function sort(collection, sortFn) {
  if (!Array.isArray(collection) || collection.length <= 1) {
    return collection;
  } else if (sortFn && typeof sortFn === "function") {
    return reduce(collection, sortFn, []);
  }

  return mergeSort(collection);
}

This implementation validates the inputs provided and utilises Merge sort as the default sorting algorithm if no sortFn function is provided.

If a sortFn function is provided, we will use our reduce function from the previous article in this series to immutably apply a sorting algorithm to our collection. 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.

To understand how the reduce function works you can check the previous article in this series.

In the tests section of this article we used Selection sort as the sortFn reducer function and you can see how simple it was to add a custom sorting algorithm like that in the test. In essence the reducer pattern being used is what makes this implementation as flexible as you need it to be in the first place while still being stable and performant.

Conclusions

In the implementation we built above, the default time complexity will always be O(n log n) and the space complexity will be O(n) when a sortFn function is not provided.

If a sortFn function is provided then the Big O will vary on your implementation for time and space complexity.

Overall though this is a stable and performant implementation which will work as expected in almost every scenario you can throw at it.

Hopefully you have learned a bit more about how sorting works in JavaScript and other languages and how implementing something of our own can improve upon the native implementations when we need to do so!

Comments

[Thor Galle]

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]

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]

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]

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.