How to make sorting HTML tables faster?

Question

I am a Javascript newbie. After trying out many Javascript and Jquery plugins to sort my HTML table and ending up disappointed, I decided to implement my own Javascript code for sorting HTML tables. The code I wrote is an update from W3Schools.

function sortFunctionNumeric(n) {
  var table, rows, switching, i, x, y, shouldSwitch, dir, switchcount = 0;
  table = document.getElementById("reportingTable");
  switching = true;
  //Set the sorting direction to ascending:
  dir = "asc";
  /*Make a loop that will continue until
  no switching has been done:*/
  while (switching) {
    //start by saying: no switching is done:
    switching = false;
    rows = table.rows;
    /*Loop through all table rows (except the
    first, which contains table headers):*/
    for (i = 1; i < (rows.length - 1); i++) {
      //start by saying there should be no switching:
      shouldSwitch = false;
      /*Get the two elements you want to compare,
      one from current row and one from the next:*/
      x = rows[i].getElementsByTagName("TD")[n];
      y = rows[i + 1].getElementsByTagName("TD")[n];
      /*check if the two rows should switch place,
      based on the direction, asc or desc:*/
      if (dir == "asc") {
        if (Number(x.innerHTML) > Number(y.innerHTML)) {
          //if so, mark as a switch and break the loop:
          shouldSwitch = true;
          break;
        }
      } else if (dir == "desc") {
        if (Number(x.innerHTML) < Number(y.innerHTML)) {
          //if so, mark as a switch and break the loop:
          shouldSwitch = true;
          break;
        }
      }
    }
    if (shouldSwitch) {
      /*If a switch has been marked, make the switch
      and mark that a switch has been done:*/
      rows[i].parentNode.insertBefore(rows[i + 1], rows[i]);
      switching = true;
      //Each time a switch is done, increase this count by 1:
      switchcount++;
    } else {
      /*If no switching has been done AND the direction is "asc",
      set the direction to "desc" and run the while loop again.*/
      if (switchcount == 0 && dir == "asc") {
        dir = "desc";
        switching = true;
      }
    }
  }
}

Now the sorting works perfectly fine. However, it is very slow!

I deal with a lot of rows of daqta(depending on project, it can go up to 9000 rows). Is there a way to speed up my Javascript code?

Answer 1

It helps to avoid implementing sorting algorithms in browser JavaScript because JavaScript's built-in Array.prototype.sort method will be much faster even if you end-up implementing the same sort algorithm (IIRC most JS engines will probably use QuickSort anyway).

Here's how I'd do it:

• Get all of the <tr> elements in a JavaScript Array.
  • You need to use querySelectorAll in conjunction with Array.from because querySelectorAll does not return an array, it actually returns a NodeListOf<T> - but you can pass this into Array.from to convert it to an Array.
• Once you have the Array, you can use Array.prototype.sort(comparison) with a custom callback to extract the data from the <td> child of the two <tr> elements being compared, and then compare the data (using the x - y trick when comparing numeric values. For string values you'll want to use String.prototype.localeCompare, e.g. return x.localeCompare( y ).
• After the Array is sorted (which should not take more than a few milliseconds for even a table with tens of thousands of rows, as QuickSort is really quick!) re-add each <tr> using appendChild of the parent <tbody>.

My implementation in TypeScript is below, along with a working sample with valid JavaScript in the script-runner located underneath:

// This code has TypeScript type annotations, but can be used directly as pure JavaScript by just removing the type annotations first.

function sortTableRowsByColumn( table: HTMLTableElement, columnIndex: number, ascending: boolean ): void {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

    rows.sort( ( x: HTMLtableRowElement, y: HTMLtableRowElement ) => {
        const xValue: string = x.cells[columnIndex].textContent;
        const yValue: string = y.cells[columnIndex].textContent;

        // Assuming values are numeric (use parseInt or parseFloat):
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum ); // <-- Neat comparison trick.
    } );

    // There is no need to remove the rows prior to adding them in-order because `.appendChild` will relocate existing nodes.
    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev: Event ): void {

    const th = ev.currentTarget as HTMLTableCellElement;
    const table = th.closest( 'table' );
    const thIndex: number = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = ( th.dataset as any ).sort != 'asc';

    sortTableRowsByColumn( table, thIndex, ascending );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }

    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

My sortTableRowsByColumn function assumes the following:

• Your <table> element uses <thead> and has a single <tbody>
• You're using a modern browser that supports =>, Array.from, for( x of y ), :scope, .closest(), and .remove() (i.e. not Internet Explorer 11).
• Your data exists as the #text (.textContent) of the <td> elements.
• There are no colspan or rowspan cells in the table.

Here's a runnable sample. Simply click the column headers to sort in ascending or descending order:

function sortTableRowsByColumn( table, columnIndex, ascending ) {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );
    
    rows.sort( ( x, y ) => {
    
        const xValue = x.cells[columnIndex].textContent;
        const yValue = y.cells[columnIndex].textContent;
        
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum );
    } );

    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev ) {
    
    const th = ev.currentTarget;
    const table = th.closest( 'table' );
    const thIndex = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = !( 'sort' in th.dataset ) || th.dataset.sort != 'asc';
    
    const start = performance.now();

    sortTableRowsByColumn( table, thIndex, ascending );

    const end = performance.now();
    console.log( "Sorted table rows in %d ms.",  end - start );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }
 
    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

window.addEventListener( 'DOMContentLoaded', function() {
    
    const table = document.querySelector( 'table' );
    const tb = table.tBodies[0];

    const start = performance.now();

    for( let i = 0; i < 9000; i++ ) {
        
        let row = table.insertRow( -1 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
    }

    const end = performance.now();
    console.log( "IT'S OVER 9000 ROWS added in %d ms.", end - start );
    
} );

html { font-family: sans-serif; }

table {
    border-collapse: collapse;
    border: 1px solid #ccc;
}
    table > thead > tr > th {
        cursor: pointer;
    }
    table > thead > tr > th[data-sort=asc] {
        background-color: blue;
        color: white;
    }
    table > thead > tr > th[data-sort=desc] {
        background-color: red;
        color: white;
    }
    table th,
    table td {
        border: 1px solid #bbb;
        padding: 0.25em 0.5em;
    }

<table>
    <thead>
        <tr>
            <th onclick="onColumnHeaderClicked(event)">Foo</th>
            <th onclick="onColumnHeaderClicked(event)">Bar</th>
            <th onclick="onColumnHeaderClicked(event)">Baz</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>1</td>
            <td>9</td>
            <td>a</td>
        </tr>
        <!-- 9,000 additional rows will be added by the DOMContentLoaded event-handler when this snippet is executed. -->
    </tbody>
</table>

A word on performance:

According to Chrome 78's Developer Tools' Performance analyzer, on my computer, the performance.now() calls indicate the rows were sorted in about 300ms, however the "Recalculate style" and "Layout" operations which happens after the JavaScript has stopped running took 240ms and 450ms respectively (690ms total relayout time, plus the 300ms sort time means it took a full second (1,000ms) from click-to-sorted).

When I changed the script such that the <tr> elements are added to an intermediate DocumentFragment instead of the <tbody> (so that each .appendChild call is guaranteed to not cause a reflow/layout, instead of just assuming that .appendChild won't trigger a reflow) and re-ran the performance test my result timing figures were more-or-less identical (they were actually slightly higher by about 120ms total after 5 repeats, for an average time of (1,120ms) - but I'll put that down to the browser JIT playing-up.

Here's the changed code inside sortTableRowsByColumn:

    function sortTableRowsByColumn( table, columnIndex, ascending ) {

        const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

        rows.sort( ( x, y ) => {

            const xValue = x.cells[columnIndex].textContent;
            const yValue = y.cells[columnIndex].textContent;

            const xNum = parseFloat( xValue );
            const yNum = parseFloat( yValue );

            return ascending ? ( xNum - yNum ) : ( yNum - xNum );
        } );

        const fragment = new DocumentFragment();
        for( let row of rows ) {
            fragment.appendChild( row );
        }

        table.tBodies[0].appendChild( fragment );
    }

I reckon the performance is relatively slow because of the Automatic Table Layout algorithm. I'll bet if I change my CSS to use table-layout: fixed; the layout times will shrink. (Update: I tested it with table-layout: fixed; and surprisingly that didn't improve performance at all - I can't seem to get better times than 1,000ms - oh well).