Is quick sort the fastest?

Average O(n log n) is fast but worst case is O(n²). Merge sort is always O(n log n).

What is stable sorting?

Sorting that preserves relative order of equal elements. Merge is stable, quick/heap are unstable.

Which sorting is used in practice?

Python uses Timsort (merge+insertion), C++ uses Introsort (quick+heap+insertion).

Advanced Sorting | Quick, Merge, Heap Sort O(n log n) Complete Guide

2026년 3월 28일 · 24분 읽기 · 수정 2026년 3월 28일 Intermediate Tutorial

이 글의 핵심

Practical guide to advanced sorting algorithms. Complete coverage of quick, merge, and heap sort O(n log n) with detailed examples.

Introduction

”The World of O(n log n)”

Advanced sorting achieves O(n log n) using divide and conquer. These are the sorting algorithms used in practice and coding interviews.

1. Quick Sort

Algorithm

Partition around pivot:

[5, 2, 8, 1, 9, 3]
pivot = 5

[2, 1, 3] 5 [8, 9]
   ↓           ↓
[1, 2, 3]   [8, 9]

Python Implementation

Below is a method that divides into three chunks left / equal / right based on pivot, then recursively sorts left and right. Creates new lists, making implementation readable and good for following divide-and-conquer flow.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# Test
arr = [5, 2, 8, 1, 9, 3]
print(quick_sort(arr))  # [1, 2, 3, 5, 8, 9]

Step-by-Step Trace:

[5, 2, 8, 1, 9, 3]
pivot=8
left=[5,2,1,3], middle=[8], right=[9]

quick_sort([5,2,1,3]):
  pivot=1
  left=[], middle=[1], right=[5,2,3]
  
  quick_sort([5,2,3]):
    pivot=2
    left=[], middle=[2], right=[5,3]
    
    quick_sort([5,3]):
      pivot=3
      left=[], middle=[3], right=[5]
      return [3,5]
    
    return [2,3,5]
  
  return [1,2,3,5]

quick_sort([9]):
  return [9]

Final: [1,2,3,5,8,9]

In-Place Implementation

def quick_sort_inplace(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Usage
arr = [5, 2, 8, 1, 9, 3]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr)  # [1, 2, 3, 5, 8, 9]

Partition Trace:

arr = [5, 2, 8, 1, 9, 3], pivot=3

i=-1, j=0: arr[0]=5 (>= 3, skip)
i=-1, j=1: arr[1]=2 (< 3, i++, swap)
  i=0, swap arr[0] and arr[1]: [2, 5, 8, 1, 9, 3]
i=0, j=2: arr[2]=8 (>= 3, skip)
i=0, j=3: arr[3]=1 (< 3, i++, swap)
  i=1, swap arr[1] and arr[3]: [2, 1, 8, 5, 9, 3]
i=1, j=4: arr[4]=9 (>= 3, skip)

Final swap arr[i+1] and arr[high]:
[2, 1, 3, 5, 9, 8]
return i+1=2

Time Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n²) (already sorted)
Space: O(log n) (recursion stack)
Stable: No

2. Merge Sort

Algorithm

Divide → Sort → Merge:

[5, 2, 8, 1]
   ↓ Divide
[5, 2] [8, 1]
   ↓ Divide
[5] [2] [8] [1]
   ↓ Merge
[2, 5] [1, 8]
   ↓ Merge
[1, 2, 5, 8]

Python Implementation

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(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test
arr = [5, 2, 8, 1, 9, 3]
print(merge_sort(arr))  # [1, 2, 3, 5, 8, 9]

Merge Process:

Merge [2, 5] and [1, 8]:

i=0, j=0: left[0]=2, right[0]=1
  1 < 2 → result=[1], j++

i=0, j=1: left[0]=2, right[1]=8
  2 < 8 → result=[1,2], i++

i=1, j=1: left[1]=5, right[1]=8
  5 < 8 → result=[1,2,5], i++

i=2 (end): result.extend([8])
  result=[1,2,5,8]

Time Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n log n) (always consistent!)
Space: O(n)
Stable: Yes

3. Heap Sort

Algorithm

Build max heap → Extract one by one:

def heap_sort(arr):
    import heapq
    
    # Use min heap
    heap = []
    for num in arr:
        heapq.heappush(heap, num)
    
    result = []
    while heap:
        result.append(heapq.heappop(heap))
    
    return result

# Test
arr = [5, 2, 8, 1, 9, 3]
print(heap_sort(arr))  # [1, 2, 3, 5, 8, 9]

In-Place Heap Sort

def heap_sort_inplace(arr):
    """
    In-place heap sort using max heap
    """
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    """
    Heapify subtree rooted at index i
    """
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Test
arr = [5, 2, 8, 1, 9, 3]
print(heap_sort_inplace(arr))  # [1, 2, 3, 5, 8, 9]

Time Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Space: O(1) (in-place possible)
Stable: No

4. Sorting Comparison

Algorithm	Average	Worst	Space	Stable	Feature
Quick	O(n log n)	O(n²)	O(log n)	No	Fastest
Merge	O(n log n)	O(n log n)	O(n)	Yes	Consistent
Heap	O(n log n)	O(n log n)	O(1)	No	In-place

When to Use Each

# Quick Sort
# - Average case performance critical
# - In-place sorting needed
# - Unstable is acceptable

# Merge Sort
# - Stable sorting required
# - Worst case O(n log n) guaranteed
# - Extra space available

# Heap Sort
# - In-place + O(n log n) guaranteed
# - Don't need stability
# - Priority queue operations

5. Practical Problems

Problem 1: Kth Largest Element

import heapq

def kth_largest(arr, k):
    """
    Kth largest number (O(n log k))
    """
    heap = []
    
    for num in arr:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    
    return heap[0]

# Test
arr = [3, 2, 1, 5, 6, 4]
print(kth_largest(arr, 2))  # 5

Using Quick Select (O(n) average):

def quick_select(arr, k):
    """
    Find kth largest using quick select
    Average O(n), worst O(n²)
    """
    if len(arr) == 1:
        return arr[0]
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x > pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x < pivot]
    
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(middle):
        return middle[0]
    else:
        return quick_select(right, k - len(left) - len(middle))

# Test
arr = [3, 2, 1, 5, 6, 4]
print(quick_select(arr, 2))  # 5

Problem 2: Merge Sorted Arrays

def merge_sorted_arrays(arr1, arr2):
    """
    Merge two sorted arrays (O(n+m))
    """
    result = []
    i = j = 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result

# Test
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
print(merge_sorted_arrays(arr1, arr2))
# [1, 2, 3, 4, 5, 6]

6. Practical Tips

Coding Interview Tips

# ✅ Use built-in sort most of the time
arr.sort()  # O(n log n)

# ✅ Understand time complexity
# - Quick: Average O(n log n), worst O(n²)
# - Merge: Always O(n log n)
# - Heap: Always O(n log n), in-place

# ✅ Know stability
# - Stable: Merge, Timsort
# - Unstable: Quick, Heap

# ✅ Space considerations
# - In-place: Quick, Heap
# - Extra space: Merge

Common Mistakes

# ❌ Wrong: Quick sort on already sorted
arr = [1, 2, 3, 4, 5]
quick_sort(arr)  # O(n²) worst case!

# ✅ Better: Use merge or built-in
arr.sort()  # Timsort handles this well

# ❌ Wrong: Forgot base case
def quick_sort(arr):
    pivot = arr[0]  # Error if arr is empty!
    # ...

# ✅ Correct: Check base case
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    # ...

Advanced Example: Stable Sort with Keys

When same scores must preserve original input order, need stable sort like insertion, merge, or Timsort.

from dataclasses import dataclass

@dataclass
class Row:
    name: str
    score: int

rows = [
    Row("A", 90),
    Row("B", 90),
    Row("C", 80),
]

# Python's sort is stable, use index as secondary key
indexed = list(enumerate(rows))
indexed.sort(key=lambda t: (-t[1].score, t[0]))
ordered = [r for _, r in indexed]
print([r.name for r in ordered])  # ['A', 'B', 'C']

Cautions

Partial sorting (top-k) may be more efficient with heap or heapq.nsmallest.
For nearly sorted arrays, insertion sort or Timsort approaches best case.

In Practice

In application code, use language built-in sorting and only define custom keys.
For large-scale data, consider external sorting (disk, chunks) and distributed frameworks.

Comparison and Alternatives

Situation	Recommendation
General list sorting	`list.sort` / `sorted`
Top-k	Heap
Uniform integer distribution	Counting sort (separate article)

Additional Resources

Python Sorting HOW TO
CLRS — Introduction to Algorithms (sorting reference)

Summary

Key Points

Quick: Pivot partition, average O(n log n), unstable
Merge: Divide and merge, always O(n log n), stable
Heap: Heap structure, O(n log n), in-place
Practice: Python Timsort, C++ Introsort

Algorithm Selection

Need	Algorithm
Fastest average	Quick
Guaranteed O(n log n)	Merge or Heap
Stable	Merge
In-place	Quick or Heap
Nearly sorted	Insertion or Timsort

Next Steps

Basic Sorting (Bubble/Selection/Insertion)

Keywords

Sorting Algorithm, Quick Sort, Merge Sort, Heap Sort, Divide and Conquer, O(n log n), Stable Sort, In-place Sort, Coding Interview, Algorithm

Advanced Sorting | Quick, Merge, Heap Sort O(n log n) Complete Guide

이 글의 핵심

Introduction

”The World of O(n log n)”

1. Quick Sort

Algorithm

Python Implementation

In-Place Implementation

Time Complexity

2. Merge Sort

Algorithm

Python Implementation

Time Complexity

3. Heap Sort

Algorithm

In-Place Heap Sort

Time Complexity

4. Sorting Comparison

When to Use Each

5. Practical Problems

Problem 1: Kth Largest Element

Problem 2: Merge Sorted Arrays

6. Practical Tips

Coding Interview Tips

Common Mistakes

Advanced Example: Stable Sort with Keys

Cautions

In Practice

Comparison and Alternatives

Additional Resources

Summary

Key Points

Algorithm Selection

Next Steps

Recommended Problems

Baekjoon

LeetCode

Programmers

Keywords

이 글의 핵심

Introduction

”The World of O(n log n)”

1. Quick Sort

Algorithm

Python Implementation

In-Place Implementation

Time Complexity

2. Merge Sort

Algorithm

Python Implementation

Time Complexity

3. Heap Sort

Algorithm

In-Place Heap Sort

Time Complexity

4. Sorting Comparison

When to Use Each

5. Practical Problems

Problem 1: Kth Largest Element

Problem 2: Merge Sorted Arrays

6. Practical Tips

Coding Interview Tips

Common Mistakes

Advanced Example: Stable Sort with Keys

Cautions

In Practice

Comparison and Alternatives

Additional Resources

Summary

Key Points

Algorithm Selection

Next Steps

Recommended Problems

Baekjoon

LeetCode

Programmers

Related Posts

Keywords