Insertion Sort 15 XP Easy

Ctrl+Enter Run Ctrl+S Save

Insertion Sort builds the sorted array one item at a time. It picks each element and inserts it into its correct position among the already-sorted elements.

Think of sorting cards in your hand — you pick up each card and slide it into the right spot.

# [5, 2, 4, 6, 1, 3]
# key=2: shift 5 right → [2, 5, 4, 6, 1, 3]
# key=4: shift 5 right → [2, 4, 5, 6, 1, 3]
# key=6: no shift needed → [2, 4, 5, 6, 1, 3]
# key=1: shift all right → [1, 2, 4, 5, 6, 3]
# key=3: shift 4,5,6 right → [1, 2, 3, 4, 5, 6]

Time: O(n²) worst, O(n) best (nearly sorted data). Space: O(1). It's the best quadratic sort for small or nearly-sorted arrays.

📋 Instructions

Implement `insertion_sort(arr)` that sorts in-place. Sort `[5, 2, 4, 6, 1, 3]` and print the result.

Loop from index 1. Save key = arr[i]. Shift elements greater than key one position right (j goes backwards). Place key at the gap.

🧪 Test Cases

Input

insertion_sort([5, 2, 4, 6, 1, 3])

Expected

[1, 2, 3, 4, 5, 6]

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›