{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "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": 31,
        "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."
        }
    ]
}