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).

[2026] Advanced Sorting | Quick, Merge, Heap Sort O(n log n) 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: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

[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. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 함수 정의 및 구현
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: 다음은 text를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

[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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

[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

다음은 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(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: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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): 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 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. 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

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

이 글의 핵심

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

Keywords

이 글의 핵심

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