Sorting algorithms pseudo-code and complexity
Filed under Accolite
Free read 1 of 3Bubble: O(n^2) time, O(1) space. Merge: O(n log n) time, O(n) space. Quick: O(n log n) average time, O(log n) space.
The question
Explain the time and space complexities of Bubble Sort, Merge Sort, and Quick Sort. Additionally, provide the logic or pseudo-code for Quick Sort, highlighting the partitioning step.
Approach
Bubble: O(n^2) time, O(1) space. Merge: O(n log n) time, O(n) space. Quick: O(n log n) average time, O(log n) space.
Pick an element as a pivot (last, first, or random) to divide the array.
Rearrange elements so those smaller than the pivot are on the left and larger are on the right.
Recursively apply the same logic to the sub-arrays formed to the left and right of the pivot.
Tips
- What they are testing: Be prepared to explain the worst-case scenario for Quick Sort (O(n^2)) and how to avoid it using random pivots.
- Common mistake: Confusing the space complexity of Merge Sort (O(n)) with Quick Sort (O(log n) for the call stack).
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.