Javascript algorithm - section list of messages by date

INTRODUCTION

I am fetching messages from my database (using bidirectional pagination (recent messages at the bottom, old messages at the top), so every time I fetch 15 messages, I section them into their respective date group.

I'm a bit stuck since the algorithm is somewhat complex if you want to get a good performance...

CODE

Here is my current code:

export default class MessagesDatesSectioner {
  constructor(
    dateOptions = {
      weekday: "short",
      year: "numeric",
      month: "short",
      day: "numeric",
    }
  ) {
    this.dateOptions = dateOptions;
    this.sections = [];
    this.sectionsRef = new Map();
  }

  /**
  * Group a list of messages by date, generating a list of sections
  * which contains a title (the messages day as string), and an array
  * of data that contains all the messages.
  *
  * @param {list of objects}     messages     [{ date, text }, ...].
  */
  sectionizeMessagesByDate(messages) {
    let sections = messages.reduce((sections, message) => {
      const key =
        message.date
          .toDate?.()
          .toLocaleDateString(undefined, this.dateOptions) ||
        message.date.toLocaleDateString(undefined, this.dateOptions);

      if (!sections[key]) {
        sections[key] = [];
      }

      sections[key].push(message);

      return sections;
    }, {});

    sections = Object.keys(sections).map((key) => ({
      title: key,
      data: sections[key],
    }));

    // Merge the resulted sections with the existed ones
    this.mergeNewMessagesSections(sections);
  }

  /**
  * Get a list of new sections (or groups of messages), and merge them
  * with the existing sections.
  *
  * @param {list of objects}     newMessagesSections     [{ title: "Monday", data: [{date, text}, ...], }, ...].
  */
  mergeNewMessagesSections(newMessagesSections) {
    for (const { title, data } of newMessagesSections) {
      if (!this.sectionsRef.has(title)) {
        this.sectionsRef.set(title, this.sections.length);
        this.sections.push({ title, data: [] });
      }

      this.sections[this.sectionsRef.get(title)].data.push(...data);
    }
  }

  deleteMessage(message) {
    // TODO
  }
  
  // Return a copy of the sections list
  getSections() {
    return [...this.sections];
  }
}

PROBLEM

My problem comes when adding data to those structures. As I am using a bidirectional pagination, the new messages might have an earlier or later date than the previously-sectioned messages.

For example:

  1- Call sectionizeMessagesByDate() with the following messages
          [
             { date: new Date("10/31/2000 00:00:01"), text: "Hello" },
             { date: new Date("10/31/2001 00:00:02"), text: "World" },
          ] // Note: All messages are sorted by date in the given array by default (Do not care about it)

  2- When merging, as there is no data in the sections list, it will generate the following:
          [
              {
                title: "10/31/2000",
                data: [ { date: new Date("10/31/2000 00:00:01"), text: "Hello" } ]  
              },
              {
                title: "10/31/2001", // Other year (different date)
                data: [ { date: new Date("10/31/2000 00:00:02"), text: "Hello" } ]  
              }
          ]  

As you can see, new sections are added to the tail of the current sections list when merging...

So, if the class generates a new section which date is "10/31/1999", it will be added to the bottom, not preserving a date order.

Any ideas how to implement the ordering (by dates) between sections and sections messages (in the data array) preserving a good performance?

Note: The map 'sectionsRef' has the title of the section as key, and it index in the sections list as value, just to achieve a O(1) complexity order when inserting messages into existing sections.