A stable sorting algorithm is one in which two equal values, A and B$,$ appear in the same relative ordering both before and after sorting. For example, given the input array $[42251],$ we can keep track of the duplicate elements by mentally labeling the duplicate $2$ elements as $2$A$$ and $2$B$$: $[42$A $2$B $51].$ A sorting algorithm is stable if it produces the following output: $[12$A $2$B $45],$ since the first $2($labeled A$)$ appears before the second $2($labeled B$)$ both before and after sorting.

Which of the following sorting algorithms are stable based on the versions discussed in lecture? Mark ALL that apply. An incorrect response will deduct partial credit.

insertion sort

selection sort

counting sort

bogosort

none of the sorting algorithms are stable