JavaSorting

Insertion Sort

Input: a₁, ... , a_n
Output: b₁, ... , b_n (the a_i's in increasing order)

An iteration of Insertion Sort:
On the j^th iteration, we have the sequence c₁,...,c_j, a_j+1,...,a_n.
Here c₁,...,c_j is the numbers a₁,...,a_j in increasing order.

1. Compare a_j+1 with c_j,c_j-1,c_j-2,... in this order until a place is found, ie when c_i < a_j+1 <= c_i+1 (or a_j+1 < c₁).
2. Insert a_j+1 between c_i and c_i+1 (or at the beginning of the list).
3. Repeat next iteration with this new c₁,...,c_j+1, a_j+2,...,a_n.

Complexity: T(n) = n(n-1)/2
Worst case running time: O(n²)
Running time for ordered list: O(n)
Running time for reversed list: O(n²)
Extra memory required: O(1)

Merge Sort

Input: a₁, ... , a_n
Output: b₁, ... , b_n (the a_i's in increasing order)

1. When n = 1, we are done.
2. For n > 1, set k = floor(n/2) and recursively sort the two sequences a₁,...,a_k and a_k+1,...,a_n.
3. Merge the two sorted sequences.

Let us see how step 3 is carried out. Suppose we want to merge two sorted sequences b₁,...,b_k and c₁,...,c_l. The first element of the merged sequence is going to be min{b₁,c₁}. Delete this minimal element from its respective sequence and place it at the first position of the merged sequence. To find the second element of the merged sequence, compare the first elements of the two new sequences, etc. If all elements of one sequence has been deleted, then the remains of the other sequence is appended at the end of the existing merged sequence, and we are done.

Recurrence formula: T(n) = T(n-k) + n
Complexity: if using recursion tree method and assuming n = 2^p, we get T(n) = 2n(log2n) = O(nlogn)
Worst case running time: O(nlogn)
Running time for ordered list: O(nlogn)
Running time for reversed list: O(nlogn)
Extra memory required: O(n)