api: YAML JSON TOON Database
version: 1.0.0
format: toon
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[2]: 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[2]: "Counting, radix and bucket sort assume a bounded key range or distribution.",Standard libraries use hybrid algorithms; textbook sorts are mainly for understanding.
  related[4]: sorting-algorithms-comparison,search-algorithms,complexity-classes,python-builtins
  entry_count: 12
  fields[7]{section,field,type,example}:
    data,name,string,Bubble Sort
    data,best,string,O(n)
    data,average,string,O(n^2)
    data,worst,string,O(n^2)
    data,space,string,O(1)
    data,stable,boolean,"true"
    data,notes,string,Simple but inefficient for large inputs.
  category: Algorithms
  category_slug: algorithms
  tags: "algorithms,sorting,complexity,big-o"
  view_count: 29
  created_at: 1792832553
  updated_at: 1792832553
data[12]{name,best,average,worst,space,stable,notes}:
  Bubble Sort,O(n),O(n^2),O(n^2),O(1),true,Simple but inefficient for large inputs.
  Selection Sort,O(n^2),O(n^2),O(n^2),O(1),false,Minimizes swaps; good when write cost is high.
  Insertion Sort,O(n),O(n^2),O(n^2),O(1),true,Efficient for small or nearly sorted datasets.
  Merge Sort,O(n log n),O(n log n),O(n log n),O(n),true,Consistent performance; good for linked lists.
  Quick Sort,O(n log n),O(n log n),O(n^2),O(log n),false,In-place; widely used in practice.
  Heap Sort,O(n log n),O(n log n),O(n log n),O(1),false,Guaranteed O(n log n); in-place.
  Counting Sort,O(n + k),O(n + k),O(n + k),O(k),true,Only for integers in bounded range.
  Radix Sort,O(nk),O(nk),O(nk),O(n + k),true,Sorts by digit position; k = number of digits.
  Timsort,O(n),O(n log n),O(n log n),O(n),true,Hybrid of merge and insertion sort that exploits existing runs; used in Python and Java for objects.
  Introsort,O(n log n),O(n log n),O(n log n),O(log n),false,"Starts as quicksort and falls back to heapsort when recursion gets too deep; common in C++ std::sort."
  Bucket Sort,O(n + k),O(n + k),O(n^2),O(n + k),true,Distributes items into buckets and sorts each; good for uniformly distributed input.
  Shell Sort,O(n log n),Depends on gap sequence,O(n^2) for simple gaps,O(1),false,Generalizes insertion sort with diminishing gaps; simple and in place.