levo
Log inStart

Recursion, Sorting and Searching

Quicksort and merge sort

  • 3 things to know
  • A2 Unit 3

Overview

Recall questions on the pivot and partitioning worked on a list, the base case, why the choice of pivot decides the worst case, the median-of-three, how two ordered lists are merged, the levels of merging, why merge sort is O(n log n) even at worst, and which suits a file too large for memory.

What you need to know

Answer each one before you reveal it.

Your recallNot started
Key term

On what principle does quicksort work?

Key term

What is the pivot in quicksort?

Key term

The list 7, 2, 9, 4, 1, 8, 5 is partitioned about the pivot 5. Which values end up on each side of it?

Questions from this subtopic

Each one with the model answer underneath.

  1. 1

    On what principle does quicksort work?

    Model answer

    Quicksort chooses a pivot value, partitions the list so that smaller values lie on one side of it and larger values on the other, then sorts each side by the same method.

  2. 2

    What is the pivot in quicksort?

    Model answer

    The pivot is the value the list is partitioned about, and it finishes the partition already in its final sorted position.

  3. 3

    The list 7, 2, 9, 4, 1, 8, 5 is partitioned about the pivot 5. Which values end up on each side of it?

    Model answer

    The values 2, 4 and 1 finish on the left of 5 and the values 7, 9 and 8 finish on its right.

  4. 4

    How does quicksort know when to stop calling itself?

    Model answer

    A sublist holding one item, or none at all, is already in order, so it is returned without being partitioned any further.

  5. 5

    Why is quicksort described as a divide-and-conquer algorithm?

    Model answer

    Each partition divides the task into two smaller sorting tasks that are solved by the same algorithm, and no work at all is needed to join the results.

  6. 6

    Under what circumstances does quicksort perform at its worst, and what does its running time become?

    Model answer

    It performs worst when every pivot turns out to be the smallest or largest value remaining, so one side of each partition is empty and the time rises to O(n²).

See the rest and revise

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.

1Closed book
2Open book
3Closed book

The 3-step method, run for you

Answer cold, learn it, then prove it stuck. Levo tracks the jump between your first attempt and your last.

Hardware: Architecture, Memory and Storage
Networks and Data Transmission
Logic Gates and Boolean Algebra
Data Representation and Data Types

Cram a whole paper in one sitting

Sort every topic into what you know and what you do not, then drill only the weak ones.

Fetch, , execute.
decodecompilestore

Blank Blitz makes facts automatic

Rapid timed gap-fills on the terms and numbers you need to recall without thinking.

AEncryption is reversible.
BThe stored form could be decrypted.
CA hash cannot be reversed.

Build It gets the exam shape right

Assemble a full-mark answer from its marking points, in the order an examiner wants them.

A bit is a single binary digit.
TrueFalse

Test It catches misconceptions

Spot the fault in a statement. The traps are the mistakes students actually make.

721941163128510

Brain Breaks between sessions

Short focus games to reset attention, so the next set lands better than the last.

Every question in Recursion, Sorting and Searching, on a schedule.

Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.

Start revising, £5 a monthSee how the method works

Or £46 a year, about £3.83 a month. Cancel anytime.