Array sort
Tags: javascript, functional
Published: 2020-02-06 21:20:27

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](https://dev.to/jamesrweb/bubble-sort-3iid), [Selection sort](https://dev.to/jamesrweb/selection-sort-1e57), [Insertion sort](https://dev.to/jamesrweb/insertion-sort-b3d), [Quick sort](https://dev.to/jamesrweb/quick-sort-4e6b) and [Merge sort](https://dev.to/jamesrweb/merge-sort-530c).

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:

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

Simple right? Different [JavaScript engines](https://en.wikipedia.org/wiki/JavaScript_engine) use different algorithms for the `sort` function but overall they produce the same result. Now, to our custom implementation!

## Tests

```javascript
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](https://dev.to/jamesrweb/selection-sort-1e57) as the algorithm in the custom `sortFn` function test.

## Implementation

The native `sort` function has the following signature:

```javascript
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:

```javascript
/**
 * @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](https://dev.to/jamesrweb/merge-sort-530c) as the default sorting algorithm if no `sortFn` function is provided.

If a `sortFn` function is provided, we will use our [`reduce` function](https://dev.to/jamesrweb/array-reduce-2bfh) 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](https://dev.to/jamesrweb/array-reduce-2bfh) you can check the previous article in this series.

In the tests section of this article we used [Selection sort](https://dev.to/jamesrweb/selection-sort-1e57) 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](https://en.wikipedia.org/wiki/Big_O_notation) 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!