Three Way Quick Sort - Coursera Algorithms

Three Way Quick Sort uses multiple partition elements, such that the there are no larger entries to their left and no smaller entries to their right. It is in place, but not a stable sort. This is used to deal with duplicate elements.

Time complexity: O(NlgN)


Following is the program, partition elements are from lt to gt:

Related Posts: 

Quick Sort

Insertion Sort 

Quick Sort - Coursera Algorithms

Quick Sort uses a partition element, such that the there are no larger entries to it's left and no smaller entries to it's right. It is in place, but not a stable sort.

Time complexity: O(NlgN)
Worst case : O(N²)

Following is the program:

Merge Sort - Coursera Algorithms

Merge sort uses divide and conquer approach to sort the elements. It takes at most NlgN compares and 6NlgN array accesses with total running time of NlgN.

Following is an optimized merge sort - it uses insertion sort for less number of elements. Please see Insertion Sort for the insertion sort algorithm. It also has a method for bottom up merge sort which is not as efficient as the recursive merge sort.

Related Posts: 

Insertion Sort

Shell Sort - Coursera Algorithms

Shell sort moves entries by more than one position at a time. It is basically insertion sort with a stride length h - it considers h interleaved sequences and sorts them using insertion sort. When the increment(h) is big, the sub-arrays are smaller and when the increment gets shorter in subsequent iterations, the array is already partially sorted. In both cases, insertion sort works great and hence, it's the best option here.

The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.

It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.

Following is the program:

Related Posts: 

Insertion Sort

Insertion Sort - Coursera Algorithms

Insertion Sort swaps an element with a larger entry to it's left.

It take ~1/4 N2 compares and ~1/4 N2 exchanges.
Best case(already sorted) : N-1 compares and zero exchanges.
Worst case(reverse sorted):  ~1/2 N2 compares and ~1/2 N2 exchanges.
Partially sorted(when number of inversions <= cN): linear time as number of exchanges equal the number of inversions.

Following is the program, it also uses shuffle to make the order as random as possible. This is done by swapping each element with a random index r such that r is between 0 and iteration i. This takes linear time.