Assignment Sample: Complexity Analysis of Sorting Algorithms

Model Answer

Introduction

Sorting is one of the most extensively studied problems in computer science, both because sorted data underpins many other algorithms – binary search, merge-based joins in databases, and priority scheduling all assume or exploit ordering – and because the sorting problem is small enough to analyse rigorously while still exposing the core trade-offs that recur throughout algorithm design (Cormen et al., 2022). This assignment analyses the time and space complexity of four comparison-based sorting algorithms: bubble sort, insertion sort, merge sort and quicksort. For each algorithm, a formal complexity derivation is presented alongside a fully worked numerical example, so that the abstract Big-O results can be checked against an explicit count of operations on a concrete array. The assignment concludes with a comparative table and a discussion of the practical circumstances under which each algorithm would, and would not, be an appropriate choice. Comparison-based sorting is used as the frame for this analysis because it is governed by a well-known Ω(n log n) lower bound, derived from an information-theoretic argument over the n! possible orderings of n elements, which gives a natural benchmark against which every algorithm below can be judged (Aho, Hopcroft and Ullman, 1983).

Approach and Method

The method adopted here follows standard practice in algorithm analysis (Knuth, 1998; Sedgewick and Wayne, 2011). For each algorithm, the number of comparisons and data movements (swaps or shifts) is counted as a function of the input size n, using the worst case unless otherwise stated, since worst-case analysis gives a guarantee that holds for every input rather than only for a favourable one. Two complementary techniques are used to derive the results: direct counting, where the total number of operations performed by nested loops is summed algebraically, and recurrence analysis, where the running time of a divide-and-conquer algorithm is expressed as a recurrence relation and solved using the substitution method and the Master Theorem (Cormen et al., 2022). Each derivation is then verified against a fully worked trace on an explicit array, so that the formula and the concrete operation count agree. Where a derivation depends on the initial ordering of the input, as with insertion sort and quicksort, both the worst case and a less pathological case are traced explicitly, since asymptotic notation alone can obscure how much practical performance varies with input order (Weiss, 2014).

Worked Analysis: Bubble Sort

Bubble sort repeatedly steps through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order, until a full pass makes no swaps. In the worst case – a reverse-sorted array – every comparison in every pass results in a swap. Consider the array A = [5, 4, 3, 2, 1], where n = 5:

Pass 1: compare(5,4)→swap → [4,5,3,2,1]; compare(5,3)→swap → [4,3,5,2,1]; compare(5,2)→swap → [4,3,2,5,1]; compare(5,1)→swap → [4,3,2,1,5]. (4 comparisons, 4 swaps)

Pass 2: compare(4,3)→swap → [3,4,2,1,5]; compare(4,2)→swap → [3,2,4,1,5]; compare(4,1)→swap → [3,2,1,4,5]. (3 comparisons, 3 swaps)

Pass 3: compare(3,2)→swap → [2,3,1,4,5]; compare(3,1)→swap → [2,1,3,4,5]. (2 comparisons, 2 swaps)

Pass 4: compare(2,1)→swap → [1,2,3,4,5]. (1 comparison, 1 swap)

The total number of comparisons is 4 + 3 + 2 + 1 = 10, which matches the general formula for the sum of the first n−1 positive integers, n(n−1)/2 = 5(4)/2 = 10. Generalising to an array of size n = 8, the worst-case comparison count is 8(7)/2 = 28, and because every comparison on a reverse-sorted array also causes a swap, the swap count is likewise 28. Since the number of operations grows with the square of n, bubble sort is O(n²) in the worst and average case, and O(n) in the best case if an early-exit flag is used to detect an already-sorted array after a pass with zero swaps (Levitin, 2012). The benefit of this optimisation is visible on a nearly-sorted array such as B = [1,2,3,4,5,6,8,7]: a single pass performs seven comparisons but only one swap (8 ↔ 7), and a confirming second pass performs seven comparisons and zero swaps before the early-exit flag halts the algorithm, giving 14 comparisons in total rather than the 28 required for the fully reverse-sorted case of the same size.

Worked Analysis: Insertion Sort

Insertion sort builds the sorted array one element at a time, taking each new element and shifting it left past any larger elements until its correct position is found. Consider the array A = [5, 2, 4, 1, 3], n = 5:

i = 1 (key = 2): compare with 5 → 5 > 2, shift; no further elements → insert 2 at index 0. Array: [2,5,4,1,3]. (1 comparison, 1 shift)

i = 2 (key = 4): compare with 5 → shift; compare with 2 → 2 < 4, stop → insert 4 after 2. Array: [2,4,5,1,3]. (2 comparisons, 1 shift)

i = 3 (key = 1): compare with 5 → shift; compare with 4 → shift; compare with 2 → shift; no further elements → insert 1 at index 0. Array: [1,2,4,5,3]. (3 comparisons, 3 shifts)

i = 4 (key = 3): compare with 5 → shift; compare with 4 → shift; compare with 2 → 2 < 3, stop → insert 3 after 2. Array: [1,2,3,4,5]. (3 comparisons, 2 shifts)

This trace totals 1 + 2 + 3 + 3 = 9 comparisons, below the absolute worst case because the starting array was not fully reverse-sorted. Repeating the same procedure on the reverse-sorted array [5,4,3,2,1] gives comparison counts of 1,2,3,4 at each step, totalling 1 + 2 + 3 + 4 = 10 = n(n−1)/2, confirming the same O(n²) worst-case bound as bubble sort. For n = 8, this gives 28 comparisons in the worst case. The key practical difference is that insertion sort’s inner loop terminates as soon as the correct position is found, so on nearly-sorted data it approaches O(n), and it is commonly used as the base case for hybrid sorts such as Timsort once a sub-array shrinks below roughly 32–64 elements (Sedgewick and Wayne, 2011). It is the shift count, not the comparison count, that dominates a naive array-based implementation, since each shift moves an element rather than merely testing it; in the reverse-sorted trace the shift totals (0,1,2,3, generalising to 0,1,…,n−1) sum to the same quadratic n(n−1)/2 bound as the comparisons, confirming the two costs are of the same asymptotic order even though they are counted separately (Goodrich, Tamassia and Goldwasser, 2014).

Worked Analysis: Merge Sort Recurrence

Merge sort splits the array in half, recursively sorts each half, and merges the two sorted halves in linear time. Its running time is expressed by the recurrence T(n) = 2T(n/2) + cn, with base case T(1) = c, where cn represents the cost of merging two sorted halves of total size n. Applying the Master Theorem (Cormen et al., 2022) with a = 2, b = 2 and f(n) = cn: the comparison term is n^log_ba = n^log₂2 = n¹ = n. Since f(n) = Θ(n) matches n^log_ba exactly, Master Theorem Case 2 applies, giving T(n) = Θ(n log n).

This result can be verified by substitution. Guess T(n) = cn log₂n + cn and check it satisfies the recurrence:

T(n) = 2[c(n/2)log₂(n/2) + c(n/2)] + cn = cn log₂(n/2) + cn + cn = cn(log₂n − 1) + 2cn = cn log₂n + cn

which matches the original guess, confirming T(n) = Θ(n log n). Numerically, for n = 8 the recursion splits the array across log₂8 = 3 levels of merging (sizes 1→2, 2→4, 4→8), and at every level the combined cost of merging is proportional to n = 8, giving a total merge cost proportional to 3 × 8 = 24, consistent with T(8) = Θ(8 log₂8) = Θ(24). Because merge sort always splits evenly, this Θ(n log n) bound holds in the best, average and worst case, at the cost of O(n) auxiliary space for the temporary arrays used during merging. This auxiliary-space requirement is a genuine trade-off rather than an implementation detail: in-place merge variants exist, but they raise the time complexity of the merge step itself, and for very large datasets close to available memory the O(n) space cost can outweigh merge sort’s time advantage (Kleinberg and Tardos, 2006). An iterative bottom-up version, which merges progressively larger runs of size 1,2,4,8,… without recursion, removes the O(log n) call-stack depth of the top-down version above while leaving the Θ(n log n) comparison bound unchanged.

Worked Analysis: Quicksort

Quicksort selects a pivot, partitions the array so that smaller elements precede the pivot and larger elements follow it, then recursively sorts each partition. Using the Lomuto partition scheme with the last element as pivot on A = [8, 3, 5, 4, 7, 6, 1, 2] (n = 8, pivot = 2):

Initialise boundary index i = −1. Scan j from index 0 to index 6, comparing each element with the pivot (2): A[0]=8>2 (no action); A[1]=3>2 (no action); A[2]=5>2 (no action); A[3]=4>2 (no action); A[4]=7>2 (no action); A[5]=6>2 (no action); A[6]=1 ≤ 2 → increment i to 0 and swap A[0] with A[6]: array becomes [1,3,5,4,7,6,8,2]. After the scan, swap A[i+1] = A[1] with the pivot at A[7]: swap 3 and 2, giving [1,2,5,4,7,6,8,3]. The pivot 2 is now fixed at index 1, splitting the array into a left partition of size 1 ([1]) and a right partition of size 6 ([5,4,7,6,8,3]).

This single partition step used exactly n − 1 = 7 comparisons, as expected. Note, however, that the resulting split (1 and 6) is highly unbalanced: this pivot happened to be close to the minimum value in the array. If a poor pivot is repeatedly chosen – for example, always choosing the last element on an already-sorted array – every partition splits off only one element, giving the recurrence T(n) = T(n−1) + Θ(n), which solves to the worst-case Θ(n²). When the pivot instead splits the array into two roughly equal halves on average, the recurrence approximates T(n) = 2T(n/2) + Θ(n), the same shape as merge sort, giving the average-case O(n log n) that makes quicksort the fastest general-purpose comparison sort in practice despite its poor worst case (Sedgewick and Wayne, 2011; Bentley and McIlroy, 1993). This average case can be made rigorous through randomised quicksort, where the pivot is drawn uniformly at random rather than fixed at a set position. Using linearity of expectation over each pair of elements, the expected comparison count can be shown to be at most 2n ln n ≈ 1.39n log₂n for every input, not merely on average over ‘typical’ inputs, since an adversary cannot target a fixed pivot rule that no longer exists (Cormen et al., 2022). Many production implementations achieve a similar guarantee more cheaply via median-of-three pivot selection, comparing the first, middle and last elements of a sub-array and using their median as pivot, which sharply reduces the probability of the unbalanced split seen in the worked trace above.

Comparative Summary

Table 1 summarises the time and space complexity of the four algorithms analysed above, together with heapsort and selection sort for wider context.

Table 1. Time and space complexity of six comparison-based sorting algorithms (Cormen et al., 2022; Skiena, 2020).

Evaluation and Discussion

The worked derivations above show that no single algorithm is optimal for every situation, which is why production sorting libraries rarely implement just one method. Merge sort’s guaranteed Θ(n log n) bound and stability make it attractive when predictable performance and preserving the relative order of equal keys both matter, for example when sorting database records by a secondary key after already sorting by a primary key; its main drawback is the O(n) auxiliary space required for merging, which can matter for very large datasets (Goodrich, Tamassia and Goldwasser, 2014). Quicksort is usually faster in practice due to better cache locality and a smaller constant factor, and its in-place partitioning needs only O(log n) stack space for recursion, but its O(n²) worst case means naive implementations can be attacked with adversarial or already-sorted input; production implementations mitigate this with randomised or median-of-three pivot selection (Bentley and McIlroy, 1993).

Insertion sort, despite its O(n²) asymptotic bound, is frequently the fastest choice for small n (typically fewer than 32–64 elements) because its low constant factor and good cache behaviour outweigh the asymptotic disadvantage at small scale; this is why hybrid algorithms such as Timsort, used in Python’s built-in sort and Java’s Collections.sort for objects, switch to insertion sort once a sub-array becomes small enough (Sedgewick and Wayne, 2011). Bubble sort has essentially no practical advantage over insertion sort at any scale and is included here chiefly for its pedagogical simplicity. Stability, illustrated in Table 1, is a further practical consideration whenever a sort is applied to composite records rather than plain numbers, since only a stable sort guarantees that ties keep their original relative order.

Conclusion

This assignment has derived and numerically verified the time and space complexity of four comparison-based sorting algorithms. Bubble sort and insertion sort were both shown, via worked traces on small arrays, to require O(n²) comparisons in the worst case, matching the closed-form n(n−1)/2. Merge sort’s recurrence T(n) = 2T(n/2) + cn was solved by both the Master Theorem and substitution to give Θ(n log n), and a worked Lomuto partition demonstrated concretely how quicksort’s performance depends on pivot quality, explaining its average-case O(n log n) alongside its O(n²) worst case. No algorithm dominates on every criterion: the choice between them depends on input size, whether stability is required, and whether worst-case guarantees or average-case speed matter more for the application at hand.

References

• Aho, A.V., Hopcroft, J.E. and Ullman, J.D. (1983) Data Structures and Algorithms. Reading, MA: Addison-Wesley.
• Bentley, J.L. and McIlroy, M.D. (1993) ‘Engineering a sort function’, Software: Practice and Experience, 23(11), pp. 1249–1265.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press.
• Goodrich, M.T., Tamassia, R. and Goldwasser, M.H. (2014) Data Structures and Algorithms in Java. 6th edn. Hoboken: Wiley.
• Kleinberg, J. and Tardos, E. (2006) Algorithm Design. Boston: Pearson.
• Knuth, D.E. (1998) The Art of Computer Programming, Volume 3: Sorting and Searching. 2nd edn. Reading, MA: Addison-Wesley.
• Levitin, A. (2012) Introduction to the Design and Analysis of Algorithms. 3rd edn. Boston: Pearson.
• Sedgewick, R. and Wayne, K. (2011) Algorithms. 4th edn. Upper Saddle River: Addison-Wesley.
• Skiena, S.S. (2020) The Algorithm Design Manual. 3rd edn. Cham: Springer.
• Weiss, M.A. (2014) Data Structures and Algorithm Analysis in Java. 3rd edn. Boston: Pearson.