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

  • Linked List: Linear-time arbitrary indexing, constant-time access to front (back), constant-time insertion and deletion

  • 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
    m ← |adiv 2
    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[0]=1 and a[1]=1 and a[2]=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