Insertion sort

|4 6 8 2 9 5 1 7 3
 4|6 8 2 9 5 1 7 3
 4 6|8 2 9 5 1 7 3
 4 6 8|2 9 5 1 7 3
 2 4 6 8|9 5 1 7 3
 2 4 6 8 9|5 1 7 3
 2 4 5 6 8 9|1 7 3
 1 2 4 5 6 8 9|7 3
 1 2 4 5 6 7 8 9|3
 1 2 3 4 5 6 7 8 9|



Selection sort

|4 6 8 2 9 5 1 7 3
 1|6 8 2 9 5 4 7 3
 1 2|8 6 9 5 4 7 3
 1 2 3|6 9 5 4 7 8
 1 2 3 4|9 5 6 7 8
 1 2 3 4 5|9 6 7 8
 1 2 3 4 5 6|9 7 8
 1 2 3 4 5 6 7|9 8
 1 2 3 4 5 6 7 8|9
 1 2 3 4 5 6 7 8 9|



Quicksort (picking the first element as the pivot)

 4 6 8 2 9 5 1 7 3
 4|6 8 2 9 5 1 7 3|
 4 3|8 2 9 5 1|7 6
 4 3 1 2|9 5 8 7 6
 2|3 1|   4   9|5 8 7 6|
 2 1|3   4   9 5 8 7 6|
 1   2   3   4   6|5 8 7|   9
 1   2   3   4   6 5|8 7    9
 1   2   3   4   5   6   8 7    9
 1   2   3   4   5   6   7   8   9



Quicksort (using the median-of-three pivot)

 4 6 8 2 9 5 1 7 3
   pivot is 4 (median of [4, 9, 3])
 4|6 8 2 9 5 1 7 3|
 4 3|8 2 9 5 1|7 6
 4 3 1 2|9 5 8 7 6
 2 3 1    4   9 5 8 7 6
   pivot is 2 (median of [2,3,1]) and 8 (median of [9,8,6])
 2|3 1|   4   8|5 9 7 6|
 2 1|3    4   8 5|9 7 6|
 1   2   3   4   8 5 6 7|9
 1   2   3   4   7 5 6   8   9
   pivot is 6 (median of [7,5,6])
 1   2   3   4   6|5 7|   8   9
 1   2   3   4   6 5|7    8   9
 1   2   3   4   5   6   7   8   9



Mergesort

 4 6 8 2 9 5 1 7 3
   (splitting)
 4 6 8 2   9 5 1 7 3
   (splitting)
 4 6   8 2   9 5   1 7 3
   (splitting)
 4 6   8 2   9 5   1   7 3
   (sorting in base cases)
 4 6   2 8   5 9   1   3 7
   (merging)
 4 6   2 8   5 9   1 3 7
   (merging)
 2 4 6 8   1 3 5 7 9
   (merging)
 1 2 3 4 5 6 7 8 9