SME
Data Structures & Algorithms · Problem type
Comparisons: quadratic sorts vs merge sort
Use this for “How many comparisons does selection sort make on 1000 items, and at most how many does merge sort make?”
Chart
A log scale: each grid line up is 10 times the one below.
This is an example. Type your own values to start a new problem.
Cq
=
n
×
(
n
−
1)
÷
2
Cₘ
=
n
×
p
r
Times as many
worked out (not typed)
Formulas
Cq
=
n
×
n
− 1
2
499,500
=
1,000
×
1,000 − 1
2
p
=
⌈log₂
n
⌉
10 = ⌈log₂ 1,000⌉
Cₘ
=
n
×
p
10,000 = 1,000 × 10
r
=
Cq
Cₘ
49.95
=
499,500
10,000
Assumptions
•
Selection sort always compares every pair once; bubble and insertion sort do the same in their worst case.
•
Merge sort makes ⌈log₂n⌉ passes, and each pass compares fewer than n times, so n⌈log₂n⌉ is an upper bound.
•
Each comparison counts as one step, the cost both sorts are measured in.
Step-by-step
WE KNOW
n = 1,000
FIND
quadratic sort comparisons (Cq), merge passes (p), merge sort comparisons (Cₘ), times as many (r)
Step 1 · Find quadratic sort comparisons (Cq)
Use Cq = n × (n − 1) ÷ 2
Each
of
the
n
items
is
compared
with
the
n
−
1
others,
and
that
counts
every
pair
twice.
Cq
=
1,000
×
1,000 − 1
2
Cq
=
1,000
×
999
2
Cq
=
999,000
2
Cq = 499,500
Step 2 · Find merge passes (p)
Use p = ⌈log₂ n⌉
Each
pass
doubles
the
length
of
the
sorted
runs,
so
p
passes
reach
n
when
2ᵖ
≥
n
.
⌈log₂
1,000⌉
=
10,
since
2
9
=
512
<
1,000
≤
1,024
=
2
10
p
=
10
Step 3 · Find merge sort comparisons (Cₘ)
Use Cₘ = n × p
Merging
two
runs
takes
at
most
one
comparison
per
item
placed,
so
each
pass
costs
at
most
n
.
Cₘ = 1,000 × 10
Cₘ = 10,000
Step 4 · Find times as many (r)
Use r = Cq ÷ Cₘ
How many times as many comparisons the quadratic sort makes.
r
=
499,500
10,000
r
=
49.95
Check
Put the numbers back in. Both sides should match.
499,500
=
1,000
×
1,000 − 1
2
✓
10 = ⌈log₂ 1,000⌉ ✓
10,000 = 1,000 × 10 ✓
49.95
=
499,500
10,000
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.