Trace the following sorting algorithm for sorting the array 7 1 9 2 3 5 into ascending order. Use the array implementation as described in the textbook/lectures.

## Insertion sort

7 1 9 2 3 5

1 7 9 2 3 5

1 7 9 2 3 5

1 2 7 9 3 5

1 2 3 7 9 5

1 2 3 5 7 9

## Selection sort

7 1 9 2 3 5 |

7 1 5 2 3 | 9

3 1 5 2 | 7 9

3 1 2 | 5 7 9

2 1 | 3 5 7 9

1 | 2 3 5 7 9

| 1 2 3 5 7 9

## Bubble sort

First pass:

7 1 9 2 3 5 → 1 7 9 2 3 5

1 7 9 2 3 5 → 1 7 9 2 3 5

1 7 9 2 3 5 → 1 7 2 9 3 5

1 7 2 9 3 5 → 1 7 2 3 9 5

1 7 2 3 9 5 → 1 7 2 3 5 9

Second pass:

1 7 2 3 5 | 9 → 1 7 2 3 5 | 9

1 7 2 3 5 | 9 → 1 2 7 3 5 | 9

1 2 7 3 5 | 9 → 1 2 3 7 5 | 9

1 2 3 7 5 | 9 → 1 2 3 5 7 | 9

Third pass:

1 2 3 5 | 7 9 → 1 2 3 5 | 7 9

1 2 3 5 | 7 9 → 1 2 3 5 | 7 9

1 2 3 5 | 7 9 → 1 2 3 5 | 7 9 (sorted)

## Mergesort

List of calls:

mergesort(theArray, 0, 5)

mergesort(theArray, 0, 2)

mergesort(theArray, 0, 1)

mergesort(theArray, 0, 0)

mergesort(theArray, 1, 1)

merge(theArray, 0, 0, 1)

mergesort(theArray, 2, 2)

merge(theArray, 0, 1, 2)

mergesort(theArray, 3, 5)

mergesort(theArray, 3, 4)

mergesort(theArray, 3, 3)

mergesort(theArray, 4, 4)

merge(theArray, 3, 3, 4)

mergesort(theArray, 5, 5)

merge(theArray, 3, 4, 5)

merge(theArray, 0, 2, 5)

## Quicksort

7 1 9 2 3 5

7 | 1 9 2 3 5          (first unknown = 1 (points to 1),  1 belongs to s1)

7 | 1 | 9 2 3 5      (9 belongs to s2)

7 | 1 | 9 | 2 3 5   (2 belongs to s1, so swap 9 and 2)

7 | 1 2 | 9 | 3 5   (3 belongs to s1, so swap 9 and 3)

7 | 1 2 3 | 9 | 5   (5 belongs to s1, so swap 9 and 5)

7 | 1 2 3 5 | 9 |   (s1 and s2 are determined)

5 1 2 3 | 7 | 9      (place the pivot between s1 and s2)

Sort the first subarray (i.e. [5 1 2 3]) and the second subarray (i.e. [9]).

5 1 2 3

5 | 1 2 3                (first unknown = 1 (points to 1), 1 belongs to s1)

5 | 1 | 2 3             (2 belongs to s1)

5 | 1 2 | 3             (3 belongs to s1)

5 | 1 2 3 |             (s1 and s2 are determined)

1 2 3 | 5 |             (place pivot between s1 and s2)

Now, the array is sorted.

List of calls:

quicksort(theArray, 0, 5)

partition(theArray, 0, 5, pivotIndex)

quicksort(theArray, 0, 3)

partition(theArray, 0, 3, pivotIndex)

quicksort(theArray, 0, 2)

partition(theArray, 0, 2, pivotIndex)

quicksort(theArray, 0, 1)

partition(theArray, 0, 1, pivotIndex)

quicksort(theArray, 0, 0)

quicksort(theArray, 2, 1)

quicksort(theArray, 3, 2)

quicksort(theArray, 4, 3)

quicksort(theArray, 5, 5)