api: YAML JSON TOON Database
version: 1.0.0
format: yaml
dataset:
  id: 2488
  slug: sorting-algorithms
  title: Sorting Algorithms
  description: Comparison of fundamental sorting algorithms with time and space complexity.
  summary: "Sorting algorithms with best, average and worst time, space, stability and notes: bubble, selection, insertion, merge, quick, heap, counting and radix sort, extended with Timsort, introsort, bucket sort and shell sort."
  use_when:
    - You need to choose a sort or explain the trade-offs among them.
    - You need to know whether a sort is stable or in place.
  caveats:
    - Counting, radix and bucket sort assume a bounded key range or distribution.
    - Standard libraries use hybrid algorithms; textbook sorts are mainly for understanding.
  related:
    - sorting-algorithms-comparison
    - search-algorithms
    - complexity-classes
    - python-builtins
  entry_count: 12
  fields:
    - section: data
      field: name
      type: string
      example: Bubble Sort
    - section: data
      field: best
      type: string
      example: O(n)
    - section: data
      field: average
      type: string
      example: O(n^2)
    - section: data
      field: worst
      type: string
      example: O(n^2)
    - section: data
      field: space
      type: string
      example: O(1)
    - section: data
      field: stable
      type: boolean
      example: "true"
    - section: data
      field: notes
      type: string
      example: Simple but inefficient for large inputs.
  category: Algorithms
  category_slug: algorithms
  tags: algorithms,sorting,complexity,big-o
  view_count: 30
  created_at: 1792832553
  updated_at: 1792832553
data:
  - name: Bubble Sort
    best: O(n)
    average: O(n^2)
    worst: O(n^2)
    space: O(1)
    stable: true
    notes: Simple but inefficient for large inputs.
  - name: Selection Sort
    best: O(n^2)
    average: O(n^2)
    worst: O(n^2)
    space: O(1)
    stable: false
    notes: Minimizes swaps; good when write cost is high.
  - name: Insertion Sort
    best: O(n)
    average: O(n^2)
    worst: O(n^2)
    space: O(1)
    stable: true
    notes: Efficient for small or nearly sorted datasets.
  - name: Merge Sort
    best: O(n log n)
    average: O(n log n)
    worst: O(n log n)
    space: O(n)
    stable: true
    notes: Consistent performance; good for linked lists.
  - name: Quick Sort
    best: O(n log n)
    average: O(n log n)
    worst: O(n^2)
    space: O(log n)
    stable: false
    notes: In-place; widely used in practice.
  - name: Heap Sort
    best: O(n log n)
    average: O(n log n)
    worst: O(n log n)
    space: O(1)
    stable: false
    notes: Guaranteed O(n log n); in-place.
  - name: Counting Sort
    best: O(n + k)
    average: O(n + k)
    worst: O(n + k)
    space: O(k)
    stable: true
    notes: Only for integers in bounded range.
  - name: Radix Sort
    best: O(nk)
    average: O(nk)
    worst: O(nk)
    space: O(n + k)
    stable: true
    notes: Sorts by digit position; k = number of digits.
  - name: Timsort
    best: O(n)
    average: O(n log n)
    worst: O(n log n)
    space: O(n)
    stable: true
    notes: Hybrid of merge and insertion sort that exploits existing runs; used in Python and Java for objects.
  - name: Introsort
    best: O(n log n)
    average: O(n log n)
    worst: O(n log n)
    space: O(log n)
    stable: false
    notes: "Starts as quicksort and falls back to heapsort when recursion gets too deep; common in C++ std::sort."
  - name: Bucket Sort
    best: O(n + k)
    average: O(n + k)
    worst: O(n^2)
    space: O(n + k)
    stable: true
    notes: Distributes items into buckets and sorts each; good for uniformly distributed input.
  - name: Shell Sort
    best: O(n log n)
    average: Depends on gap sequence
    worst: O(n^2) for simple gaps
    space: O(1)
    stable: false
    notes: Generalizes insertion sort with diminishing gaps; simple and in place.