Skip to content

Multisort via Composition

Sorting a collection of data in a single dimension is pretty straightforward in most programming languages. It's quite common to use some sort of comparison interface that exposes a function with two parameters of the type being sorted, and expected return values of -1, 0, or 1.

For example, JavaScript has Array.prototype.sort, C# has IComparer, and PHP has usort.

This works quite well when you want to sort on a single property:

const data = [
  {
    first: "Emma",
    last: "Smith",
    age: 33,
  },
  {
    first: "Noah",
    last: "Johnson",
    age: 1,
  },
  {
    first: "Olivia",
    last: "Williams",
    age: 95,
  },
  {
    first: "Liam",
    last: "Jones",
    age: 77,
  },
  {
    first: "Sophia",
    last: "Brown",
    age: 54,
  },
  {
    first: "Mason",
    last: "Davis",
    age: 91,
  },
  {
    first: "Ava",
    last: "Miller",
    age: 38,
  },
  {
    first: "Jacob",
    last: "Smith",
    age: 89,
  },
  {
    first: "William",
    last: "Moore",
    age: 48,
  },
  {
    first: "Isabella",
    last: "Johnson",
    age: 24,
  },
];

data.sort((person1, person2) => person1.age - person2.age);

However if you want to sort by multiple properties using a single sort method, things can start to get messy:

data.sort((person1, person2) => {
  const lastCMP = person1.last.localeCompare(person2.last);
  if (lastCMP) {
    return lastCMP;
  }

  return person1.first.localeCompare(person2.first);
});

Now, certainly this contrived example can be simplified somewhat:

data.sort(
  (person1, person2) =>
    person1.last.localeCompare(person2.last) ||
    person1.first.localeCompare(person2.first)
);

but if the sorting algorithm needs any sort of deep access into the objects being sorted, the sorting method will turn into a mess.

More importantly, once you have a messy sort callback, making updates in the future can be more of a challenge.

Ideally, sorting could be done more declaratively. With a single sort function, it's trivially easy to write:

const byLastName = (person1, person2) =>
  person1.last.localeCompare(person2.last);
data.sort(byLastName);

and

const byFirstName = (person1, person2) =>
  person1.first.localeCompare(person2.first);
data.sort(byFirstName);

It would be annoying to have to write a new byLastThenFirstName function that calls those two separate functions (even using the concise form from earlier):

const byLastThenFirstName = (person1, person2) =>
  byLastName(person1, person2) || byFirstName(person1, person2);

It would be nicer to compose these separate functions into a single function without all the extra (person1, person2) repetition.

This can be done with a simple multisort function:

const multisort =
  (...sorters) =>
  (a, b) => {
    for (const sorter of sorters) {
      const cmp = sorter(a, b);
      if (cmp) {
        return cmp;
      }
    }
    return 0;
  };

The multisort function can be fed a collection of sorter functions to produce a new sorter function that walks through each sorter in the collection and uses the first non-zero result.

This makes the implementation for byLastThenFirstName much more concise:

const byLastThenFirstName = multisort(byLastName, byFirstName);

Also, because multisort is a function, it can be passed parameters dynamically such as when sorting the rows in a table based on columns a user has selected:

// columnSorters = [byColumnC, byColumnA, byColumnB, ...]
tableOfData.sort(multisort(...columnSorters));