D1 Algorithms – Sorting PhysicsAndMathsTutor.

com

1. 650 431 245 643 455 134 710 234 162 452

(a) The list of numbers above is to be sorted into descending order. Perform a Quick Sort to
obtain the sorted list, giving the state of the list after each pass, indicating the pivot
elements.
(5)

The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold
in one metre lengths.

(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be
cut from the minimum number of one metre lengths. (You should ignore wastage due to
cutting.)
(4)

(c) Determine whether your solution to part (b) is optimal. Give a reason for your answer.
(2)
(Total 11 marks)

2. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are

0.6, 4.0, 2.5, 3.2, 0.5, 2.6, 0.4, 0.3, 4.0 and 1.0

Guttering is sold in 4 m lengths.

(a) Carry out a quick sort to produce a list of the lengths needed in descending order. You
should show the result of each pass and identify your pivots clearly.
(5)

(b) Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the
total number of 4 m lengths needed.
(4)

(c) Does the answer to part (b) use the minimum number of 4 m lengths? You must justify
your answer.
(2)
(Total 11 marks)

Edexcel Internal Review 1

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

3. Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan

(a) Use the quick sort algorithm to sort the above list into alphabetical order.
(5)

(b) Use the binary search algorithm to locate the name Louis.
(4)
(Total 9 marks)

4. 52 48 50 45 64 47 53

The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain
the sorted list, giving the state of the list after each completed pass.
(Total 4 marks)

5.
Ali 74
Bobby 28
Eun-Jung 63
Katie 54
Marciana 54
Peter 49
Rory 37
Sophie 68

The table shows the marks obtained by students in a test. The students are listed in alphabetical
order. Carry out a quick sort to produce a list of students in descending order of marks. You
should show the result of each pass and identify your pivots clearly.
(Total 5 marks)

Edexcel Internal Review 2

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

6. 650 431 245 643 455 134 710 234 162 452

(a) The list of numbers above is to be sorted into descending order. Perform a Quick Sort to
obtain the sorted list, giving the state of the list after each pass, indicating the pivot
elements.
(5)

The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold
in one metre lengths.

(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be
cut from the minimum number of one metre lengths. (You should ignore wastage due to
cutting.)
(4)

(c) Determine whether your solution to part (b) is optimal. Give a reason for your answer.
(2)
(Total 11 marks)

7. 45, 56, 37, 79, 46, 18, 90, 81, 51

(a) Using the quick sort algorithm, perform one complete iteration towards sorting these
numbers into ascending order.
(2)

(b) Using the bubble sort algorithm, perform one complete pass towards sorting the original
list into descending order.
(2)

Another list of numbers, in ascending order, is

7, 23, 31, 37, 41, 44, 50, 62, 71, 73, 94

(c) Use the binary search algorithm to locate the number 73 in this list.
(4)
(Total 8 marks)

Edexcel Internal Review 3

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

8.
1. Glasgow
2. Newcastle
3. Manchester
4. York
5. Leicester
6. Birmingham
7. Cardiff
8. Exeter
9. Southampton
10. Plymouth

A binary search is to be performed on the names in the list above to locate the name Newcastle.

(a) Explain why a binary search cannot be performed with the list in its present form.
(1)

(b) Using an appropriate algorithm, alter the list so that a binary search can be performed.
State the name of the algorithm you use.
(4)

(c) Use the binary search algorithm on your new list to locate the name Newcastle.
(4)
(Total 9 marks)

9. The following list gives the names of some students who have represented Britain in the
International Mathematics Olympiad.

Roper (R), Palmer (P), Boase (B), Young (Y), Thomas (T), Kenney (K), Morris (M),
Halliwell (H), Wicker (W), Garesalingam (G).

(a) Use the quick sort algorithm to sort the names above into alphabetical order.
(5)

(b) Use the binary search algorithm to locate the name Kenney.
(4)
(Total 9 marks)

Edexcel Internal Review 4

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

10. 25 22 30 18 29 21 27 21

The list of numbers above is to be sorted into descending order.

(a) (i) Perform the first pass of a bubble sort, giving the state of the list after each
exchange.

(ii) Perform further passes, giving the state of the list after each pass, until the
algorithm terminates.
(5)

The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm.

(b) (i) Show the result of applying the first fit decreasing bin packing algorithm to this
situation.

(ii) Determine whether your solution to (b) (i) has used the minimum number of 50 cm
rods.
(4)
(Total 9 marks)

Edexcel Internal Review 5

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

1. (a) E.g:
650 431 245 643 455 710 234 162 452 134 M1
650 643 710 455 431 245 234 162 452 134 A1
650 710 643 455 431 245 452 234 162 134 A1 ft
710 650 643 455 431 452 245 234 162 134 A1 ft
710 650 643 455 452 431 245 234 162 134 A1

(b) Bin 1 710 + 245 Bin 3 643 + 162 + 134 Bin 5 431 M1A1
Bin 2 650 + 234 Bin 4 455 + 452 A1A1(ft) 4

4116
(c) = 4.116 5 bins needed optimal M1A1(ft) 2
1000
[11]

2. (a)
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 2.6
4.0 3.2 4.0 2.6 0.6 2.5 0.5 0.4 0.3 1.0 3.2 0.4 M1
4.0 4.0 3.2 2.6 0.6 2.5 0.5 1.0 0.4 0.3 4.0 0.5 A1
4.0 4.0 3.2 2.6 0.6 2.5 1.0 0.5 0.4 0.3 2.5 A1ft
4.0 4.0 3.2 2.6 2.5 0.6 1.0 0.5 0.4 0.3 1.0 A1ft
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3 A1 cso 5

Notes
1M1 Pivot, p, chosen. List sorted, >p, p.
<p or <p, p, >p. If only choosing 1
pivot per iteration M1 only
1A1 1st pass correct and chosen next two
pivots correctly for sublists >1
2A1ft 2nd pass correct and chosen next two
pivots correctly for sublists >1
3A1ft 3rd pass correct and next pivot for
sublist >1 chosen correctly.
4A1 cso.

Misread in part (a)

• If they have misread a number at
the start of part (a), so genuinely
miscopied and got for example 0.1
instead of 1.0 then mark the whole
question as a misread – removing the
last two A or B marks earned. This
gives a maximum total of 9.
• If they misread their own numbers

Edexcel Internal Review 6

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

during the course of part (a) then count

it as an error in part (a) but mark parts
(b) and (c) as a misread. So they would
lose marks in (a) for the error and then
the last two A or B marks earned in (b)
and (c) – giving a maximum of 8 or maybe
7 marks depending on how many marks
they lose in (a).
The most popular misread is the one listed above – where
1.0 has changed to 0.1 giving
4.0 4.0 3.2 2.6 2.5 0.6 0.5 0.4 0.3 0.1 at the end of (a) for
this one (b) and (c)
are:

(b) Length 1: 4
Length 2: 4
Length 3: 3.2 0.6 left column & 1.0 in place M1
Length 4: 2.6 1.0 0.4 0.6 & 0.5 A1
Length 5: 2.5 0.5 0.3 0.4 A1
All correct (c.s.o) A1 4
Note
Length 1: 4
Length 2: 4
Length 3: 3.2 0.6 0.1
Length 4: 2.6 0.5 0.4 0.3
Length 5: 2.5

(c) 19.1/4 = 4.775 so 5 lengths needed, accept

total is 19.1m, or refer to 0.9 ‘spare . B1
Yes, the answer to (b) does use the minimum
number of bins. DB1 2
Note
18.2/4 = 4.55 so 5 bins, or total is 18.2 or 1.8 ‘spare’
Yes answer in (b) uses the minimum number of bins.

Alternate
Choosing middle left
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.5)
0.6 4.0 2.5 3.2 2.6 4.0 1.0 0.5 0.4 0.3 (pivots 3.2, 0.4)
4.0 4.0 3.2 0.6 2.5 2.6 1.0 0.5 0.4 0.3 (pivots 4.0, 2.5)
4.0 4.0 3.2 2.6 2.5 0.6 1.0 0.5 0.4 0.3 (pivot 0.6)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3

Edexcel Internal Review 7

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

Choosing first
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
4.0 2.5 3.2 2.6 4.0 1.0 0.6 0.5 0.4 0.3 (pivots 4.0, 0.5)
4.0 2.5 3.2 2.6 4.0 1.0 0.6 0.5 0.4 0.3 (pivots 2.5, 0.4)
4.0 3.2 2.6 4.0 2.5 1.0 0.6 0.5 0.4 0.3 (pivot 3.2)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3

OR (alternate choosing first)

0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
4.0 2.5 3.2 2.6 4.0 1.0 0.6 0.5 0.4 0.3 (pivots 4.0, 0.5)
4.0 4.0 2.5 3.2 2.6 1.0 0.6 0.5 0.4 0.3 (pivots 2.5, 0.4)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3 (pivots 3.2)
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3
4.0 4.0 3.2 2.6 2.5 1.0 0.6 0.5 0.4 0.3

Sorting into ASCENDING order (full marks if then reversed, otherwise MISREAD)

Middle left
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.5)
0.4 0.3 0.5 0.6 4.0 2.5 3.2 2.6 4.0 1.0 (pivots 0.4, 3.2)
0.3 0.4 0.5 0.6 2.5 2.6 1.0 3.2 4.0 4.0 (pivots 2.5, 4.0)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0 (pivot 0.6)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0

Middle right
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 2.6)
0.6 2.5 0.5 0.4 0.3 1.0 2.6 4.0 3.2 4.0 (pivots 0.4, 3.2)
0.3 0.4 0.6 2.5 0.5 1.0 2.6 3.2 4.0 4.0 (pivots 0.5, 4.0)
0.3 0.4 0.5 0.6 2.5 1.0 2.6 3.2 4.0 4.0 (pivot 2.5)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0 (pivot 1.0)

First (1)
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
0.5 0.4 0.3 0.6 4.0 2.5 3.2 2.6 4.0 1.0 (pivots 0.5, 4.0)
0.4 0.3 0.5 0.6 2.5 3.2 2.6 1.0 4.0 4.0 (pivots 0.4, 2.5)
0.3 0.4 0.5 0.6 1.0 2.5 3.2 2.6 4.0 4.0 (pivot 3.2)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0

First (2)
0.6 4.0 2.5 3.2 0.5 2.6 0.4 0.3 4.0 1.0 (pivot 0.6)
0.5 0.4 0.3 0.6 4.0 2.5 3.2 2.6 4.0 1.0 (pivots 0.5, 4.0)
0.4 0.3 0.5 0.6 2.5 3.2 2.6 1.0 4.0 4.0 (pivots 0.4, 2.5)
0.3 0.4 0.5 0.6 1.0 2.5 3.2 2.6 4.0 4.0 (pivot 3.2)
0.3 0.4 0.5 0.6 1.0 2.5 2.6 3.2 4.0 4.0
[11]

Edexcel Internal Review 8

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

3. (a)
M J E K H B L P N D B M1 1A1
B M J E K H L P N D H
B E D H M J K L P N DL 2A1ft
B D E H J K L M P N (E) K P
B D E H J K L M N P (J) N 3A1ft
B D E H J K L M N P (M)

Sort completed 4A1 5

Note
1M1: quick sort, pivots, p, identified,
two sublists one <p one >p.
If choosing one pivot only per iteration,
M1 only.
1A1: first pass correct, next pivot(s)
chosen consistently.
2A1ft: second pass correct, next pivot(s)
chosen consistently
3A1ft: third pass correct, next pivot(s)
chosen consistently
4A1: cso List re-written or end statement
made or each element been chosen
as a pivot.

1 + 10 
(b)  2  = 6 Katie reject left M1

 7 + 10 
 2  = 9 Natsuko reject right 1A1

7 + 8
 2  = 8 Miri reject right 2A1ft

7 = Louis name found 3A1 4

Note
1M1: binary search, choosing pivot rejecting
half list.
If using unordered list then M0.
If choosing J M1 ony
1A1: first two passes correct, condone
‘sticky’pivots here, bod.
2A1ft: third pass correct, pivots rejected.
3A1: cso, including success statement.

Edexcel Internal Review 9

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

Special case
If just one letter out of order, award
maximum of M1A1A0A0
[9]

4. e.g. 52 48 50 45 64 47 53 M1
52 50 48 54 47 53 45
52 50 54 48 53 47 45 A1
52 54 50 53 48 47 45
64 52 53 50 48 47 45 A1ft
64 53 52 50 48 47 45 A1 4
No further changes – list sorted

M1 Bubble sort – 1st pass complete – end term 64 or 45,

consistent L → R or R → L shuffle, Quick etc gets M0
A1 First 2 passes correct} condone shrinking list
A1ft Next 2 passes correct (if L → R next pass} condone shrinking list
A1 Final pass and final statement/rewritten list cso – must see whole list
[4]

Notes
Bubble R → L
52 48 50 45 64 47 53 M1
64 52 48 50 45 53 47
64 53 52 48 50 45 47 A1
64 53 52 50 48 47 45 A1
No further changes – list sorted A1

Misreads – sorting into ascending order

(note – if candidates reverse list full credit is gained.

L → R (ascending – misread) MR
52 48 50 45 64 47 53 M1
48 50 45 52 47 53 64
48 45 50 47 52 53 64 A1
45 48 47 50 52 53 64
45 47 48 50 52 53 64 A1
No further changes – list sorted A1
(4-2 for misread)

Edexcel Internal Review 10

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

R→L
52 48 50 45 64 47 53 M1
45 52 48 50 47 64 53
45 47 52 48 50 53 64 A1
45 47 48 52 50 53 64
45 47 48 50 52 53 64 A1
No further changes – list sorted A1
(4-2 for misread)

74 28 63 54 54 49 37 68 54 M1
74 63 54 68 54 28 49 37 54 49 A1
74 63 68 54 49 28 37 63 37
5. e.g. 4
74 68 63 37 28 68 (28) A1ft
74 68 28
74 68 63 54 54 49 37 28 sort complete A1

∴Ali, Sophie, Eun–Jung, {Katie + Marciana}, Peter, Rory, Bobby A1

M1 Pivot clear list > P >. Bubble sort etc. M0
A1 1st pass correct, next pivots correctly selected
consistently
A1ft 2nd + 3rd passes correct, pivots for next pan selected
consistently each time. Penalise fragmented list here
(or lists rewritten or all chosen as pivots)
A1 c.s.o. + stop statement (o.e.). Penalise non-sig no.
errors here. Penalise “sloppyness” here
A1 c.a.o. accept c.a. even if MR
[5]

Alternative correct answers

(i)

74 28 63 54 54 49 37 68 54 M1
74 63 68 54 28 54 49 37 63 49 A1
74 68 63 54 49 28 37 68 37 (54)
74 68 54 37 28 A1ft

Edexcel Internal Review 11

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

(ii)

74 28 63 54 54 49 37 68 54 M1
74 63 54 68 54 28 49 37 63 49 A1
74 68 63 54 49 28 37 74 28 (54)
74 68 54 37 28 A1ft

(iii)

74 28 63 54 54 49 37 68 54 M1
74 63 68 54 28 54 49 37 63 54 A1
74 68 63 54 28 49 37 74 49
74 68 49 28 37 28 (68)
37 28 (37) A1ft

1st in list
(iv)

74 28 63 5449 54 37 68 74 M1
74 28 63 5449 54 37 68 28
63 54 5437 49 68 28 63 A1ft
68 63 5449 54 37 (68) 54
68 5449 54 37 54
49 54 37 49
49 37 (37) A1
74 68 63 54 54 49 37 28
Ali, Sophie, Eun-Jung, Katie + Marciana, Peter, Rory, Bobby

MISREADS (–2 for MR)

(a)
MR
74 28 63 54 54 49 37 68 54 M1
28 54 49 37 54 74 63 68 49 63 A1
28 37 49 54 63 74 68 37 68 (54)
28 37 54 68 74 A1ft

(b)
MR
74 28 63 54 54 49 37 68 54 M1
28 49 37 54 74 63 54 68 49 54 A1
28 37 49 54 74 63 68 37 63
28 37 63 74 68 68 (28)
68 74 A1ft

Edexcel Internal Review 12

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

(c)
MR
74 28 63 54 54 49 37 68 54 M1
28 54 49 37 54 74 63 68 54 63 A1
28 49 37 54 63 74 68 49 74
28 37 49 68 74 28
28 37
A1ft

(d)
MR
74 28 63 54 54 49 37 68 54 M1
28 49 37 54 74 63 54 68 49 63 A1
28 37 49 54 63 74 68 28 74 (54)
28 37 54 68 74 A1ft

If candidates reverse list then restore full marks.

names or numbers
Bobby, Rory, Peter, Katie + Marciana, Eun-Jung, Sophie, Ali

6. (a) E.g. M1 A1 A1ft A1ft A1 5

650 431 245 643 455 710 234 162 452 134
650 643 710 455 431 245 234 162 452 134
650 710 643 455 431 245 452 234 162 134
710 650 643 455 431 452 245 234 162 134
710 650 643 455 452 431 245 234 162 134

(b) Bin 1 710 + 245 Bin 3 643 + 162 + 134 Bin 5 431 M1 A1
Bin 2 650 + 234 Bin 4 455 + 452 A1ft A1 4
(c) eg.
4116
= 4.116 ∴ 5 bins needed ∴ optimal M1 A1ft 2
1000
[11]

7. (a) eg. 45 37 18 46 56 79 90 81 51
or 37 18 45 56 79 46 90 81 51
or 45 37 46 18 51 56 79 90 81 M1A1 2

(b) 56 45 79 46 37 90 81 51 18
or 90 45 56 37 79 46 18 81 51 M1A1 2

Edexcel Internal Review 13

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

1 + 11 
(c)  2  = 6 value 44 discard top M1
 
 7 + 11 
 2  = 9 value 71 discard top A1
 
10 + 11 
 2  = 11 value 94 discard bottom A1
 
list reduces to 10th value. This is 73 so
73 has been located as the 10th value A1 4
[8]

8. (a) The list is not in alphabetical order B1 1

(b) Use of Bubble Sort or Quick Sort M1
e.g.
Bubble sort

G N M Y L B C E S P
B G N M Y L C E P S 1st pass
B C G N M Y L E P S 2nd pass
B C E G N M Y L P S 3rd pass
B C E G L N M Y P S 4th pass
B C E G L M N P Y S 5th pass
B C E G L M N P S Y 6th pass

No more changes
Quick sort

G N M Y L B C E S P
B G N M Y L C E S P 1st pass
B G C E L N M Y S P 2nd pass
B C G E L N M S P Y 3rd pass
B C E G L N M P S Y 4th pass
B C E G L M N P S Y 5th pass
B C E G L M N P S Y 6th pass

No sublists > 2 and no more changes

A1 A1ft
No more changes No sublists > 2 + no more changes A1cso 4

Edexcel Internal Review 14

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

(c) 1 2 3 4 5 6 7 8 9 10
B C E G L M N P S Y
[10 + 1]
=6 Manchester discard first half of list and pivot M1 A1
2
[7 + 10]
= 9 Southampton discard last half of list and pivot
2
[7 + 8]
=8 Plymouth discard last half of list and pivot A1ft
2
Final term 7 Newcastle ∴ word found at 7 A1cso 4
[9]

9. (a) e.g.

R P B Y T K M H W G
M1
B H G K R P Y T M W A1
B G H K R P M T Y W A1 ft
A1 ft
B G H K M P R T W Y A1 ft
B G H K M P R T W Y

10 + 1 
(b)  2  = 6 Palmer; reject Palmer → Young M1 A1
 
 5 + 1
 2  = 3 Halliwell; reject Boase → Halliwell A1
 
4 + 5
 2  = 5 Morris; reject Morris
 
List reduces to Kenney – name found, search complete A1 4
[9]

10. (a) (i) le ft to right or right to le ft

25 22 30 18 29 21 27 21 25 22 30 18 29 21 27 21 M1
25 30 22 18 29 21 27 21 25 22 30 18 29 27 28 21
25 30 22 29 18 21 27 21 25 22 30 29 18 27 21 21
25 30 22 29 21 18 27 21 25 30 22 29 18 27 21 21
25 30 22 29 21 27 18 21 30 25 22 29 18 27 21 21 A1 (pass)
(ii) 25 30 22 29 21 27 21 18 30 29 25 22 27 18 21 21
30 25 29 22 27 21 21 18 30 29 27 25 22 21 18 21
30 29 25 27 22 21 21 18 30 29 27 25 22 21 21 18
30 29 27 25 22 21 21 18 30 29 27 25 22 21 21 18

Edexcel Internal Review 15

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

30 29 27 25 22 21 21 18

(b) (i) rod 1 30 18

2 29 21
3 27 22 M1 (to the 22)
4 25 21 A1 2

(ii) 193 ÷ 50 = 3.86, ∴ 4 rods needed, so minimum M1 A1 2

[9]

Edexcel Internal Review 16

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

1. No Report available for this question.

2. Many candidates scored at least 8 marks here. In part (a) a minority produced an ascending list
and failed to reverse it. Some candidates did not choose their pivots consistently, swapping
between middle right and middle left pivots. The decimals here caused some problems and even
though the original list was printed in the answer booklet, a surprising number of candidates
initially lost one item or changed one, most commonly 1.0 became 0.1. Some candidates found
only one pivot per row, with some not explicitly choosing pivots when sublists of length 2
happened to be in order – most frequently the two 4.0s and the 1.0, 0.6 at the end. Good
presentation, with a list spread evenly, in columns, across the page, helps here. (Vertical listing
is rarely successful). Part (b) was generally well done, the two most popular errors being to put
0.6 in bin 5 or 0.4 in bin 5. A significant number who had sorted the numbers into increasing
order in part (a) proceeded to use a “first fit increasing” method here. In part (c) most candidates
calculated the lower bound correctly. Other candidates correctly stated that since the five largest
items were over half a bin in size they could not share a bin, so at least 5 bins would be needed.
A few simply stated ‘yes’ without justification, gaining no credit.

3. This was generally well done. A disappointingly large number of candidates only chose one
pivot per iteration, rather than choosing one pivot per sublist, and some candidates used lengthy
methods of presentation that isolated each sublist in turn, making it difficult to see if they were
choosing more than one pivot per iteration. The examiners would advise candidates to refrain
from showing this unnecessary detail and simply indicate the pivots selected at each iteration.
Some candidates did not select a pivot where the sublist was of order two, with the two items
being in the correct order, and some did not consistently pick ‘middle left’ or ‘middle right’
when the sublist was of even order. Candidates are reminded that when the items are being
transferred to the next line, the order of the items should be preserved, so if item Y is to the left
of item X in the current line, neither of them being a pivot, then Y should be to the left of X in
the next line. The best candidates allowed each item to become a pivot before declaring the sort
complete. Some candidates did not check that their final list was in alphabetical order. In part
(b) some candidates tried to apply the algorithm to the original unsorted list given at the start of
(a) and others did not discard the pivot at each stage, but generally the binary search was very
well done. A few candidates selected J as the first pivot, the specification makes it clear that
candidates must take the ‘middle right’ where necessary.

4. This proved a good starter question for the candidates, with the vast majority scoring full marks.
Only a few candidates sorted the list into ascending order, and very few incorrect methods were
seen, but a disappointing number of candidates did not seem to be aware that a bubble sort
should be performed consistently in one direction. Amongst those candidates using the correct
method, more marks were lost by those misreading their own writing and changing one number
into another than those lost making errors in applying the algorithm. Some candidates omitted a
‘stop’ statement. Candidates were asked to give the state of the list after each pass, but many
showed each exchange and some each comparison, which wasted time, many of these
candidates needed to use additional sheets to show all of this working and many got into time
difficulties later on in the paper.

Edexcel Internal Review 17

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

5. The vast majority of candidates showed that they understood the concept of quick sort, with
very few bubble sorts seen. Most candidates chose to start with one of the 54’s as a pivot and a
number of candidates were unsure what to do with the second 54. Some chose 2 pivots initially,
or created an incorrect order where the two 54s were next to each other. However, most
candidates dealt well with this situation. Other common errors were: not identifying a pivot
towards the end of the quick sort, where two numbers were already in the correct order,
fragmenting the list rather than selecting pivots concurrently and the regularly seen re-ordering
of the sub-lists. Many candidates did not produce a list of students in order.

6. Some very good answers were seen to part (a), but many candidates produced disappointing
attempts. Poor presentation and lack of concentration accounted for most errors in part (a); there
was inconsistent choice of pivots, numbers that disappeared from the list, numbers that mutated
into other numbers and, of course, numbers being reordered in the list. A large minority sorted
the list into ascending order. A number of candidates are only selecting one pivot per pass,
which rather defeats the object of a quick sort. Only a very few Bubble sorts were seen.
Candidate would help themselves hugely by not fixing the position of the pivots until the line
after they are selected, this would avoid the need to try to cram numbers into the ever-
decreasing space formed by their previously chosen pivots. Candidates could then use the whole
width of the line each time. Part (b) was usually well done. Some used the first fit algorithm and
many put 134 into bin 5 rather than bin 3. Part (c) was often well attempted with the majority of
candidates giving a clear, arithmetical argument.

7. This was generally well done. Many candidates completed the quick sort, wasting time. Some
candidates did not understand the difference between an exchange and a pass in a bubble sort.
Most candidates carried out the search well, but many did not give the location of the value. A
large number are still assuming that the item is in the list, making statements such as ‘down to
one item so found’. A surprisingly large minority of candidates used the mean of the end
numbers in the remaining list to create a ‘pivot’ which is unacceptable.

8. This question was often well answered. Most candidates correctly competed part (a), although a
very few stated that the list should be in ascending rather than alphabetical order. Most could
correctly name and use a suitable sorting algorithm in part (b), although some did not make their
stopping statement clear and a few used a shuttle sort (not in this specification) stating that it
was a bubble sort. A surprisingly large minority confused the order of the alphabet with S and P
(and then M and N) most frequently transposed. Part (c) was usually well done but candidates
must make their pivots – and the order in which they select their pivots, clear. Candidates must
remember to discard their pivots and note that the specification instructs them to ‘round up’.
Once again the stopping/found statement was sometimes missing, and some candidates assumed
the presence of N, stating that once they had got down to 1 term only, that term must be N.

Edexcel Internal Review 18

D1 Algorithms – Sorting PhysicsAndMathsTutor.com

9. Many candidates were able to gain full marks on this question. The most common errors in part
(a) were in re-ordering the letters in the sub-lists and choosing the pivots inconsistently. A
surprising number of candidates seemed unsure of the alphabet. Part (b) was well done by the
majority of candidates. A surprising number tried to use an unsorted list for their search, gaining
no marks and others omitted to discard the pivot. The commonest error was in failing to select
Morris after correctly selecting Palmer then Halliwell. A few candidates did not make the order
in which they selected the pivots clear making it impossible to give credit.

10. Most candidates were able to complete the bubble sort correctly, although a number of shuttle
sorts were seen from a few candidates. A number of candidates did not complete a final pass,
(or stated that they had performed a final pass and found no further exchanges). The majority
were able to complete the bin packing but a number were unable to show that they had used a
minimum number of bins, once again the lower bound would have helped here.

Edexcel Internal Review 19