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 Complete Guide

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

이 글의 핵심

Master advanced sorting algorithms: quick, merge, and heap sort O(n log n). Learn divide-and-conquer principles, implementations, and practical applications.

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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Master advanced sorting algorithms: quick, merge, and heap sort O(n log n). Learn divide-and-conquer principles, impleme… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

정렬 알고리즘 | 버블, 선택, 삽입 정렬 완벽 정리
배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
[Binary Search | O(log n) Search Algorithm Complete Guide](/en/blog/algorithm-series-09-binary-search/

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Sorting, Quick Sort, Merge Sort, Heap Sort, Divide and Conquer 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Keyboard Shortcuts

이 글의 핵심

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

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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?