Best sort algorithm (merge sort) will take at worst.

Quick Sort


  1. Choose pivot
  2. Everything left of pivot is smaller, everything right of it is bigger ()
  3. Call quicksort on the left side and right side

Choosing a good pivot

  • Random
    • With high probability pivot within
    • Likely Complexity:
  • DSelect i.e. Median of medians approach
    • Rank is guaranteed to be between of the array slice
    • Complexity: ……first term: DSelect, second term quicksort
      • for some (=)

Merge Sort


  1. Split into two
  2. Call mergesort on each left, right side
  3. merge left, right side in time

alg. Parallel Merge Idea: For the 8 elements shown below, can we find out how to place the element in parallel (8 simultaneous processes)? → We can!

  • Left half: binary search on right half for correct place
  • Right half: binary search on left half for correct place
def PMerge(A[1..n], m)
	# Ind[i] stores the final index of the i-th element
	# left half
	parallel for i=1 to m
		# search in right half
		Ind[i] <- BinarySearch(in A[m+1..n] for A[i]) + i
	# right half
	parallel for j=m+1 to n
		# search in left half
		Ind[i] <- BinarySearch(in A[1..m] for A[j]) - m + j
	# place each item in their ordered location
	parallel for i=1 to n
		B[Ind[i]] <- A[i]
	parallel for i=1 to n
		A[i] <- B[i]
  • Span

then we have… alg. Parallel Merge Sort

def PMergeSort(A[1..n])
	# base case
	if n > 1
		m = ceiling(n/2)
	spawn PMergeSort(A[1..m])
	spawn PMergeSort(A[m+1..n])
  • Span
  • Work
    • Second term is work done by parallel merge procedure: correctly placing items, each takes .

alg. Inversion Counting. In an unsorted array count how many pairs are not in the correct order

  • Idea: Mergesort, but during the merge step check how many times you need to reverse the pairs

Partially Sorted

Uses of partially sorted arrays:

  • Top items: e.g. Google Search, College Admissions
  • -th largest/smallest item

-th smallest item (=item of rank ) => use Tournament Tree