Quick Sort

This is used in research code when built-in qsort does not satisfy the demands.

K-th element

Qsort can be used to find the Kth smallest element a[k]:

Use partition to sort 0, 0, 0, 1, 1, 2, 2, 2…

 

Merge Sort

Linked List Version

Here is the merge sort when qsort does not work:

Array Version

 

Merge

Given two sorted arrays A and B, merge B into A:

What about Lists?

Bucket Sort

O(n)

Find the first missing positive

 

Bubble Sort

O(n^2)

Sort 4 Elements