Js: What is the most efficient way to sort an array of objects into sections?

I have a large array of objects, similar to this:

[
  {
    id: "some_id",
    timestamp: 12345
  },
  {
    id: "some_other_id",
    timestamp: 12347
  },
  {
    id: "some_id",
    timestamp: 12346
  },
  {
    id: "some_other_id",
    timestamp: 12348
  },
  ...
]

I want to sort the array in a way, that there are “sections” of objects in the array, depending which id the object has. Inside each section, the objects should be sorted ascending depending on the timestamp. The sections themselves should also be sorted depending on the first timestamp of the section. So the array should look like this:

[
  // section: some_id
  {
    id: "some_id",
    timestamp: 12345
  },
  {
    id: "some_id",
    timestamp: 12348
  },
  // section: some_other_id, comes ofter some_id section because 12346 > 12345
  {
    id: "some_other_id",
    timestamp: 12346
  },
  {
    id: "some_other_id",
    timestamp: 12347
  },
  ...
]

It should also be possible to chose between ascending/descending in the function. Right now i have this:

elements.sort((a, b) => {
  if (a.id === b.id) {
    if (sortAscending) {
      return a.timestamp > b.timestamp ? -1 : 1;
    } else {
      return a.timestamp > b.timestamp ? 1 : -1;
    }
  } else {
    return a.id.localeCompare(b.id);
  }
})

This doesn’t sort the sections correctly however. Any ideas?

Answer

This will require two passes through the array because you can’t sort by sections until you know what the order of the sections should be and you don’t know that until you’ve seen all the sections and thus know what the lowest or highest timestamp is for each section (depending upon whether you’re doing ascending or descending sort).

So, probably what makes sense is to make a first pass that collects the extreme value for each section and stores it into a Map object that you can use as a section sort index. Then, you can run .sort(). If the sections are the same, you sort by timestamp. If the sections are not the same, you sort by the value in the section index.

function sortByIdAndTimestamp(data, sortAscending = true) {
    // create a Map object where keys are id values and values are the extreme
    // timestamp for that id
    const extremeTimestamp = new Map();
    for (let item of data) {
        if (testExtreme(item.timestamp, extremeTimestamp.get(item.id), sortAscending)) {
            extremeTimestamp.set(item.id, item.timestamp);
        }
    }
    // now just do a dual key sort
    data.sort((a, b) => {
        let result;
        if (a.id === b.id) {
            // if id is the same, just sort by timestamp
            result = b.timestamp - a.timestamp;
        } else {
            // if id is not the same, sort by the extreme timestamp of the id
            result = extremeTimestamp.get(b.id) - extremeTimestamp.get(a.id);
        }
        if (sortAscending) {
            result = -result;
        }
        return result;
    });
    return data;
}

function testExtreme(val, extremeSoFar, sortAscending) {
    // determine if this id's timestamp is more extreme
    // than what we already have for that section
    return (extremeSoFar === undefined) || (sortAscending ?
        val < extremeSoFar :
        val > extremeSoFar);
}

const sampleData = [{
        id: "some_id",
        timestamp: 12345
    },
    {
        id: "some_other_id",
        timestamp: 123
    },
    {
        id: "some_id",
        timestamp: 12346
    },
    {
        id: "some_other_id",
        timestamp: 99999
    },
    {
        id: "yet_another_id",
        timestamp: 1
    },
    {
        id: "yet_another_id",
        timestamp: 90000
    },
];

sortByIdAndTimestamp(sampleData, true);
console.log(sampleData);

Note: When you said you wanted to sort in either ascending or descending order, I assumed you meant that for both sections and for timestamps. So, an ascending sort would have the lowest timestamp section first and then the items within each section would be sorted by timestamp from low to high. And, a descending sort would have the highest timestamp section first and then items within each section would be sorted by timestamp from high to low.