# Basic Sorting: Selection, Insertion, Merge

Bart Massey

### Sorting Basics

SEQUENCE SORTING (global)

Instance: A sequence s of elements drawn from a
total-ordered set S (with an operation ≤)

Problem: Find a sequence t drawn from S s.t.
t ∈ perm(s) ∧ ∀ ij ∈ 1..|S| . i < j => t[i] ≤ t[j]

SEQUENCE SORTING (local)

Instance: A sequence s of elements drawn from a
total-ordered set S (with an operation ≤)

Problem: Find a sequence t drawn from S s.t.
t ∈ perm(s) ∧ ∀ i ∈ 2..|S| => t[i-1] ≤ t[i]

Provably the same

• local → global via transitive property of <
• global → local via subsumption

### Representations of A Sequence

• Array: Constant-time index for reading and writing, linear-time editing

• Others: Many, many others

• Fundamental array operation: swap two elements, using constant time and space

``````  t ← a
a ← b
b ← t
``````

### Selection Sort

• Idea: Find the least element and put it first. Repeat until done.

ALGORITHM SELECTION SORT
To sort a:
for i ← 1..|a|
for j ← i+1..|a|
if a[j] < a[i]
a[i] ←→ a[j]

• Partial correctness by induction on i

• Always does n-1,n-2,..,1 comparisons/swaps where |s|=n, so Θ(n2)

ALGORITHM SELECTION SORT
To sort s:
t ← empty
while s is not empty
let i be the index of a minimum element of s
append s[i] to t
delete s[i] from s
return t

### Insertion Sort

• Idea: Take each element and put it where it goes in the partially ordered list, until you run out of elements

• "Dual" of selection sort

ALGORITHM INSERTION SORT
To sort a:
for i ← 2..|a|
v ← a[i]
for j ← 1..i
if v < a[j]
break
for k ← i downto j
a[k] ← a[k-1]
a[j] ← v

### Merge Sort

ALGORITHM MERGE SORT

To sort an array a
mergesort(a):
if |a| = 0
return
mergesort(a[1..m])
mergesort(a[m+1..|a|])
b ← merge(a[1..m], a[m+1..|a|])
copy b into a

To merge arrays a1 and a2:
b ← array of |a1| + |a2| elements
i1 ← 1
i2 ← 1
j ← 1
while j ≤ |b|
if i1 > |a1|
b[j] ← a2[i2]
i2 ← i2 + 1
else if i2 > |a2|
b[j] ← a1[i1]
i1 ← i1 + 1
else if a1[i1] > a2[i2]
b[j] ← a2[i2]
i2 ← i2 + 1
else
assert a1[i1] ≤ a2[i2]
b[j] ← a1[i1]
i1 ← i1 + 1
j ← j + 1
return b

### Merge Sort Complexity

• Merge is O(|b|): while loop runs once per element of b

• Master Theorem: O(|a| lg |a|)

### Exercise: Sorting AP Integers

• Arbitrary-Precision integers have an unbounded size

• We will represent AP integers as arrays of bits in binary in big-endian order. So when |a|=3 and a=1 and a=1 and a=0 we're looking at a 6.

• Give an algorithm for comparing two AP integers, and give its big-O

• Given this, describe the big-O complexity of selection sort of an array b of AP integers