Search code examples
databasesortingwebmultiple-columnscolumnsorting

Is multi column sorting an expensive operation?

{
  A: "numeric",
  B: "numeric",
  C: "numeric",
}

In general, what is the time complexity of sorting by multiple columns?

I have never found a website that has an option for multi-column sorting. That begs the question, is this operation simply to costly?

Solution

  • If the number of columns that you are sorting by is constant, than it doesn't factor into the big O runtime complexity of the sorting algorithm.

    The different columns are handled in the comparator. Pseudo code for that is:

    if column A values different
  compare values from column A
else if column B values different
  compare values from column B
else if column C values different
  compare values from column C
else 
  they are equal

    The first thing column you are sorting by is usually the only column consulted. The others are just used for tie breakers. It doesn't matter if you are sorting just one column or several, your sorting algorithm is still going to run in O(n*log(n)) time complexity.