Linearithmic (O(n log n))

At a glance: Roughly logarithmically many levels each process a total of n elements.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

Picture splitting an array into halves again and again, then rebuilding the answer from smaller sorted pieces. At each merging level, every element is inspected a constant number of times. The number of levels grows with log₂(n).

For n = 8, a balanced binary split has roughly three levels; for n = 16, roughly four. At each level of merge sort the total merge work is O(n). Multiplying gives T(n) = O(n log n), not O(log n) merely because the algorithm divides the input.

The merge-sort recurrence

Merge sort divides a sequence into halves and then merges the two sorted halves. On a balanced split, the recursion has about log₂(n) levels. At each level, the disjoint merges collectively touch all n elements, so the total work is about n operations per level. Combining the two dimensions gives Θ(n log n) worst-case time under constant-cost comparisons and moves.

A useful recurrence is T(n) = 2T(n/2) + Θ(n) for equal halves. The two recursive terms account for sorting each half, and Θ(n) accounts for merging. The logarithm comes from the height of the recursion tree; the extra n comes from work performed across every level. Merely noticing that the input is halved would incorrectly suggest O(log n).

Comparison sorting has a general Ω(n log n) worst-case lower bound when sorting arbitrary distinct elements using only comparisons. Non-comparison sorts may exploit restricted keys to achieve different bounds. A library’s actual algorithm and guarantee depend on that library; don’t label Array.Sort or std::sort as merge sort without checking its contract.

Worked example

For n = 1,024, log₂(n) = 10, so a model with ten full passes touches on the order of 10,240 elements. For n = 2,048, eleven passes produce about 22,528 touches. Doubling the input yields a little more than twice the work.

Count work by level

For eight elements, the bottom merge level merges four pairs of one-element runs, the next level merges two pairs of length-two runs, and the top level merges the two length-four runs. Each level moves or processes all eight elements, giving roughly 8 × 3 = 24 units of level work (a teaching model, not an exact comparison count).

For 16 elements there are four such levels, or roughly 64 units. For 1,024 elements there are ten, or about 10,240. This pattern explains why doubling the input makes total work a little more than double rather than exactly quadrupling as in quadratic growth.

Time complexity

Representative time example: Merge sort / divide-and-conquer merges.

Merge sort gives a reliable O(n log n) worst-case bound when merges are linear and splitting is balanced. Comparison sorting generally has an Ω(n log n) worst-case lower bound for arbitrary distinct values; this statement does not apply to every specialized non-comparison sort. The implementation below actually performs the split and merge operations rather than delegating the work to a library sorter. Its time bound is derived from those operations, not inferred from a method name.

Count merge work, not only comparisons at the root

During a merge, pointers advance through the left and right sorted runs. Every element is copied or emitted once, so merging runs whose combined length is m takes Θ(m) work. Across a complete level, those m values sum to n. There are Θ(log n) levels for balanced splitting, leading to Θ(n log n) total work.

This analysis assumes an O(1) cost per comparison and element move. If the values are very large objects or comparison examines long strings, the cost per operation also matters. It also assumes the splitting or merging implementation does not repeatedly make unnecessarily expensive copies beyond the standard merge process. The canonical guarantee comes from the algorithm and implementation, not a method name alone.

C#

C# | Linearithmic.cs

static void MergeSort(int[] values)
{
  int[] temp = new int[values.Length];
  SortRange(values, temp, 0, values.Length);
}

static void SortRange(int[] a, int[] temp, int start, int end)
{
  if (end - start <= 1) return;
  int mid = start + (end - start) / 2;
  SortRange(a, temp, start, mid);
  SortRange(a, temp, mid, end);

  int left = start, right = mid;
  for (int k = start; k < end; k++)
  {
      if (left < mid && (right == end || a[left] <= a[right]))
          temp[k] = a[left++];
      else
          temp[k] = a[right++];
  }
  Array.Copy(temp, start, a, start, end - start);
}

C++

C++ | linearithmic.cpp

#include <algorithm>
#include <vector>

void sortRange(std::vector<int>& a, std::vector<int>& temp,
             int start, int end) {
  if (end - start <= 1) return;
  int mid = start + (end - start) / 2;
  sortRange(a, temp, start, mid);
  sortRange(a, temp, mid, end);

  int left = start, right = mid;
  for (int k = start; k < end; ++k) {
      if (left < mid && (right == end || a[left] <= a[right]))
          temp[k] = a[left++];
      else
          temp[k] = a[right++];
  }
  std::copy(temp.begin() + start, temp.begin() + end,
            a.begin() + start);
}

void mergeSort(std::vector<int>& values) {
  std::vector<int> temp(values.size());
  sortRange(values, temp, 0, static_cast<int>(values.size()));
}

Analysis: Each merge level processes Θ(n) elements, and there are Θ(log n) levels. This implementation therefore takes Θ(n log n) time in the worst case and uses Θ(n) additional buffer space.

Both examples implement top-down merge sort with one reusable buffer. The merge uses <= so equal values retain their relative order. The analysis assumes element comparisons and moves have constant cost.

Space complexity

Representative memory example: An n × log n table.

A table with n rows and about log₂(n) columns stores O(n log n) cells. This is the memory example for the class O(n log n), not the usual auxiliary-space analysis of merge sort. An ordinary array-based merge sort often allocates O(n) merge-buffer storage plus O(log n) recursion frames. Its time and space therefore belong to different classes, and copying every level into a retained table is a different algorithm.

Why merge sort usually uses linear extra space

Typical top-down merge sort uses a temporary array holding up to n elements while merging. Its extra buffer is Θ(n), while the recursion stack is Θ(log n), giving Θ(n) auxiliary space overall because the linear buffer dominates. An optimized implementation can allocate one reusable buffer and pass it through recursive calls instead of allocating a fresh array at every level.

The separate n by (log n) table illustrates a different memory class, Θ(n log n). Such a table retains values for all n rows across logarithmically many columns at the same time. It is not required for ordinary merge sort. If you allocate new arrays for recursive slices and keep all ancestors’ allocations alive, peak space needs a separate lifetime analysis; do not assume a sum over levels without checking which buffers overlap.

C#

C# | Linearithmic.cs

// Assumes n >= 1; check dimensions and allocation limits.
int levels = (int)Math.Log2(n);
int[,] table = new int[n, levels + 1];

C++

C++ | linearithmic.cpp

#include <vector>
#include <cmath>

// Assumes n >= 1 and a representable allocation size.
int levels = static_cast<int>(std::log2(n));
std::vector<std::vector<int>> table(n, std::vector<int>(levels + 1));

Analysis: An n-by-(log n) table occupies O(n log n) cells; merge sort usually needs O(n) auxiliary storage, not O(n log n).

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

When linearithmic time is useful

Merge sort is valuable when you need predictable O(n log n) worst-case comparison-based sorting. It can be stable when equal values are merged in original relative order. A stable sort is especially helpful when sorting records by multiple keys. However, the usual array implementation pays an extra-memory cost that an in-place approach may avoid.

Other Θ(n log n) patterns include heap-based sorting and processing n operations that each take Θ(log n), such as certain balanced-tree insertions. Both reach the same total class for different reasons. When reviewing code, ask whether n items each pay logarithmic work, or whether there are logarithmically many levels with linear total work per level.

Practical example: sorting match results

After a multiplayer match, a scoreboard might sort n player results by score and then by a tie-breaker. A stable merge sort can preserve the original order for entries with equal keys, which helps when sorting by multiple criteria in successive passes. Its worst-case comparison work grows as Θ(n log n), but its usual temporary array also uses Θ(n) extra storage.

If the scoreboard is very small, another algorithm may be simpler or faster in practice. If the server sorts thousands of results repeatedly, the predictable growth becomes more useful. For a production API, verify the documented stability and complexity of the actual implementation; choosing a function named Sort does not by itself guarantee a specific algorithm.

Common mistake

Watch out: Do not assume the number of recursion levels alone equals total running time. Sum the work on all nodes at each level. Also distinguish a retained per-level table from a temporary buffer reused across levels.

Try it yourself

Trace merge sort on eight values and count the amount of merging on each level. Then draw the peak live buffer and stack usage.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes