15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 9 of 12 in the free DSA Basics course · 10 lessons
Build a model for sorting an array into ascending order. Choose a basic sorting method when its assumptions are known, trace array states, implement it, and describe its time and extra-memory use.
Start with comparison sorts, where the algorithm learns order by comparing values. Then use two core operations—merging and partitioning—to build recursive sorts. Finish with heap-based and restricted-domain methods, which use additional structure or assumptions about the values.
There are no required earlier topics.
Be comfortable reading arrays, accessing values by index, using loops and conditionals, swapping or shifting array values, and writing simple recursive functions with a base case.
Use this array throughout the path:
1[4, 2, 3, 1]Its ascending sorted result is:
1[1, 2, 3, 4]Different methods reach that result in different ways:
4 rightward through adjacent swaps, establishing a sorted suffix.1 and place it first, establishing a sorted prefix.3, partition smaller and larger values around it, then sort the two sides.For stability, imagine values are records with a key and an ID:
1[(2,A), (4,B), (2,C), (1,D)]A stable sort must keep (2,A) before (2,C) in the output. The numeric order alone cannot check stability; also check the order of equal keys.
Sorting Contracts and Properties defines what a correct ascending sort must produce and gives the terms used throughout the path: permutation, stability, in-place behavior, and auxiliary space.
Bubble Sort, Selection Sort, and Insertion Sort come next because their array changes are easy to trace. Each teaches a different established region: a sorted suffix, a sorted prefix built by minimum placement, or a sorted prefix built by insertion.
Merging Sorted Runs appears before Merge Sort because Merge Sort uses merging as its combine step.
Merge Sort uses recursive splitting plus the merge operation to sort larger arrays.
Partitioning Around a Pivot comes before Quick Sort because Quick Sort uses partitioning.
Quick Sort recursively sorts the regions created by a partition and shows why partition balance affects running time.
Heapify and Heap Sort adds an approach based on the max-heap property, merging, or pivot partitioning.
Counting, Radix and Bucket Sorting finishes the path with methods that require explicit domain assumptions about the input values.
Every algorithm is judged by the same contract: the output must contain exactly the input values and must be nondecreasing, meaning every adjacent pair satisfies a[i] <= a[i+1]. Sorting Contracts and Properties introduces the checks used to verify later implementations.
The three elementary comparison sorts build tracing skill before recursion. In Bubble Sort, a full pass places one large value into its final position at the end. In Selection Sort, each outer step places the smallest remaining value at the front. In Insertion Sort, each step expands an already sorted prefix. These visible invariants let you reason about correctness without a full recursive call tree.
Merge Sort and Quick Sort both use recursion and require different preparation:
The recursive methods also have different cost patterns. Merge Sort performs merging across recursion levels and typically allocates an auxiliary array. Quick Sort partitions in place in a common implementation, and its time depends on whether pivots repeatedly create balanced or unbalanced sides.
Heap Sort provides another comparison-based option. It uses the array itself as a max-heap, so it can sort with constant auxiliary space while repeatedly restoring heap order after moving the maximum to its final position.
The final lesson asks what is known about the values. Counting Sort needs a bounded integer range. LSD Radix Sort needs stable passes over digits. Bucket Sort needs a stated bucket rule and an input distribution or numeric range that makes the buckets useful. Their bounds must include domain parameters, not only array length.
Start with Sorting Contracts and Properties. For [4, 2, 3, 1], verify that [1, 2, 3, 4] is both a permutation of the input and nondecreasing. Then use tagged equal keys to test stability.
Trace Bubble Sort, Selection Sort, and Insertion Sort on the same input. After every outer pass or iteration, write down the portion whose required property is already established.
Compare the three elementary methods on an already sorted input such as [1, 2, 3, 4] and a reversed input such as [4, 3, 2, 1]. Count comparisons, swaps, or shifts at a beginner level.
Practice Merging Sorted Runs with adjacent runs such as [2, 4] and [1, 3]. Track left, right, and output positions, including what happens when one run is exhausted.
Move to Merge Sort after you can trace each merge step. Split [4, 2, 3, 1] down to arrays of length one, then merge upward to the final result.
Practice Partitioning Around a Pivot separately. Choose a stated pivot, trace scans and swaps, and check that all values on the required side satisfy the pivot relation.
Use that partition trace in Quick Sort. Draw the recursive subarrays and verify that recursive calls exclude the pivot once it is in its final position.
Learn Heapify and Heap Sort by first identifying parent and child indices in a zero-based array. Then trace sifting down, bottom-up heap construction, and repeated removal of the maximum.
Finish with Counting, Radix and Bucket Sorting. Before tracing any method, state its allowed input domain. For example, use Counting Sort only when values are nonnegative integers in a known bounded range, and use stable digit passes for LSD Radix Sort.