Sorting puts data in order, which makes searching and processing far more efficient. You need to understand four algorithms and compare how they behave.

Bubble sort and insertion sort

Bubble sort repeatedly compares neighbouring items and swaps them if they are in the wrong order. After each pass the largest unsorted item has “bubbled” to the end.

REPEAT
  Swapped <- FALSE
  FOR i <- 1 TO n - 1
    IF A[i] > A[i + 1] THEN
      Temp <- A[i]
      A[i] <- A[i + 1]
      A[i + 1] <- Temp
      Swapped <- TRUE
    ENDIF
  NEXT i
UNTIL Swapped = FALSE

Stopping when a pass makes no swaps helps on nearly sorted data. Worst case time is O(n^2).

Insertion sort builds a sorted section at the front. It takes the next item and shifts larger sorted items right until the correct gap appears, then drops the item in. It is O(n^2) in the worst case but very quick on nearly sorted data, and efficient for small lists.

Merge sort

Merge sort uses divide and conquer: split the list in half repeatedly until each part has one item, then merge the sorted halves back together by repeatedly taking the smaller front item.

[38, 27, 43, 3] -> [38, 27] [43, 3] -> [38] [27] [43] [3]
merge -> [27, 38] [3, 43] -> [3, 27, 38, 43]

It is O(n log n) in every case and stable, but needs extra memory for the merged lists.

Quicksort

Quicksort picks a pivot, partitions the list so smaller items are on the left and larger on the right, then sorts each part recursively. It is O(n log n) on average and works in place, but O(n^2) in the worst case, for example if the pivot is always the smallest value in sorted data. Choosing the middle or a random pivot helps.

Comparison

Algorithm Best Worst Extra memory Notes
Bubble O(n) O(n^2) None Simple, slow
Insertion O(n) O(n^2) None Good for small/nearly sorted
Merge O(n log n) O(n log n) O(n) Consistent
Quicksort O(n log n) O(n^2) Small (stack) Fast in practice

For 1,000 items, an n^2 sort needs about a million steps, while n log n needs about ten thousand.

Check your understanding

What does one pass of bubble sort guarantee?

  • The list is fully sorted
  • The largest unsorted item reaches its final place
  • The smallest item moves first
  • Nothing

Answer: The largest unsorted item reaches its final place. Further passes sort the remainder.

Which algorithm uses divide and conquer and always runs in O(n log n)?

  • Bubble sort
  • Insertion sort
  • Merge sort
  • Linear search

Answer: Merge sort. Its cost is the extra memory used.

What is the worst case of quicksort?

  • O(n)
  • O(log n)
  • O(n^2)
  • O(1)

Answer: O(n^2). It occurs when pivots split the list very unevenly.

Which sort is quick on nearly sorted data and needs no extra memory?

  • Insertion sort
  • Merge sort
  • Hash sort
  • Binary sort

Answer: Insertion sort. Few items need to move.

PreviousNext