SyntaxShelf

Merge sort

2 snippets in Interview Prep

DSAInterview Prep

O(n log n) - Linearithmic Time

DSA · Big-O Notation
Syntax
Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work per level.
Example
// JavaScript
// Merge sort achieves O(n log n) guaranteed
const sorted = [5, 2, 8, 1, 9].sort((a, b) => a - b);
// Built-in sort: V8 uses TimSort → O(n log n)

# Python
# Python's sorted() uses TimSort → O(n log n)
result = sorted([5, 2, 8, 1, 9])
# list.sort() is in-place, also O(n log n)
Output
Time: O(n log n) | Space: O(n) for merge sort, O(log n) for quicksort avg

Note O(n log n) is the theoretical lower bound for comparison-based sorting. If an interviewer asks you to do better, the input must have special structure (e.g., bounded integers for counting sort). Heap operations on n elements also yield O(n log n).

Merge Sort

DSA · Sorting
Syntax
Divide array in half, recursively sort each half, merge the sorted halves.
Merge step: two pointers comparing elements from each half.
Example
// JavaScript
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  return result.concat(a.slice(i), b.slice(j));
}

# Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result
Output
merge_sort([38,27,43,3,9,82,10]) → [3,9,10,27,38,43,82]

Note Time: O(n log n) always. Space: O(n). Stable. Guaranteed O(n log n) regardless of input - unlike quicksort. Preferred for linked lists (no random access needed, O(1) space merge). The merge function is reusable in many problems.

Frequently asked questions

How do you merge sort?
Interview Prep covers this with 2 copy-ready snippets on this page. The "O(n log n) - Linearithmic Time" snippet in Interview Prep uses `Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work...`.
Which code does the Interview Prep example use?
The "O(n log n) - Linearithmic Time" snippet uses `Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work...`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "merge sort"?
Besides "O(n log n) - Linearithmic Time", this page also shows "Merge Sort".
Is there anything to watch out for?
Yes. For "O(n log n) - Linearithmic Time": O(n log n) is the theoretical lower bound for comparison-based sorting. If an interviewer asks you to do better, the input must have special structure (e.g., bounded integers for counting sort). Heap operations on n elements also yield O(n log n).

Browse all tasks by intent