← Back to mit.katmh.com

Dynamic Arrays, Sorting

· Read 02/24/2021

Sequence Implementations

Cont. from last time

Dynamic Array Sequence

  • Can we improve on the (regular) array sequence, which requires O(n)O(n) to add new elements?
  • Yes! Over-allocate additional space when you request space for the array
  • If we do it right, we can guarantee that any sequence of nn insertions only takes O(n)O(n) time, and takes O(1)O(1) time per insertion on average
  • This is called amortized constant time, because the cost of the operation is amortized across many applications of the operation
  • Our strategy: allocate extra space in proportion to the size of the array being stored (any fraction works for the amortized bound)
  • Why? Because O(n)O(n) additional space ensures that a linear number of insertions must occur before an insertion will overflow the allocation
  • Often, implementations will allocate double the amount of space needed to store the current array, known as table doubling
  • When the length of the array becomes sufficiently small, we reallocate, making sure there remains a linear fraction of unused allocated space when we rebuild
  • This guarantees that Ω(n)\Omega(n) sequential dynamic operations must occur before the next time we need to reallocate memory


  • Next pointer of last node of linked list points to earlier node in list, creating a cycle. Given a pointer to the head of the list (without knowing its size), describe a linear-time algorithm to find the number of nodes in the cycle. Use only constant additional space outside the original linked list.
  • Given a data structure implementing the Sequence interface, use it to implement the Set interface. Doesn't need to be efficient.

Faster Sets

  • We've reduced the Set interface to the Sequence Interface, or simulated one with the other. But everything takes linear time.
  • To do better, we can store our items in a sorted array, so we can use binary search to find keys and support Order operations


  • Incremental: maintain and grow a sorted subset of items until all items are sorted
  • Selection sort maintains and grows a subset of the largest ii items in sorted order, while insertion does the first ii items

Selection Sort

  • Already sorted smallest items into sub-array A[:i], so repeatedly scan rest of array for smallest item not yet sorted, then swap with item A[i]
  • Can require Ω(n2)\Omega(n^2) comparisons, worst case O(n)O(n) swaps

Insertion Sort

  • Already sorted sub-array A[:i], so repeatedly swap item A[i] with item to its left until the left item is no larger than A[i]
  • Can require Ω(n2)\Omega(n^2) comparisons, worst case Ω(n2)\Omega(n^2) swaps

In-place and Stability

  • In-place: can be implemented using at most a constant amount of additional space
  • Stable: items having the same value will appear in the sort in the same order as they appeared in the input array

Merge Sort

  • Recursively sorts left and right half of array, then merges the two halves in linear time
  • Recurrence relation: T(n)=2T(n/2)+Θ(n)T(n) = 2T(n/2) + \Theta(n), which solves to T(n)=Θ(nlogn)T(n) = \Theta(n \log n)

    • logn\log n grows slower than any polynomial nϵn^{\epsilon} for ϵ>0\epsilon > 0
  • Not in-place: uses a linear amount of temporary storage
  • Whether or not it's stable depends on how an implementation breaks ties when merging

Build a Sorted Array

  • Preprocessing: spend extra time building the data structure to speed up order queries later