Sorting summary

1. Selection Sort - Θ(n^2)
- pseudocode:

SELECTION-SORT(A)
1 for i = 1 to A.length-1
2     smallest = i
3     for j = i + 1 to A.length
4         if A[smallest] > A[j]
5             smallest = j
6     temp = A[smallest]
7     A[smallest] = A[i]
8     A[i] = temp

- C++ code:

template<class T>
void selection_sort(vector<T>& A)
{
    for (int i = 0; i < A.size() - 1; ++i)
    {
        int smallest = i;

        for (int j = i + 1; j < A.size(); ++j)
            if (A[smallest] > A[j])
                smallest = j;

        int temp = A[smallest];
        A[smallest] = A[i];
        A[i] = temp;
    }
}

2. Insertion Sort - Θ(n^2)
- pseudocode:

INSERTION-SORT(A)
1 for j = 2 to A.length
2     key = A[j]
3     // Insert A[j] into the sorted sequence A[1.. j-1].
4     i = j - 1
5     while i > 0 and A[i] > key
6         A[i + 1] = A[i]
7         i = i - 1
8     A[i + 1] = key

- C++ code:

template<class T>
void insertion_sort(vector<T>& A)
{
    for (int j = 1; j < A.size(); ++j)
    {
        T key = A[j];

        int i = j - 1;
        while (i >= 0 && A[i] > key)
        {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;
    }
}

template <class T>
void insertion_sort_recursive(vector<T>& A, int key_index, int array_size)
{
    if (key_index >= array_size) return;

    T key = A[key_index];

    int i = key_index - 1;
    while (i >= 0 && A[i] > key)
    {
        A[i + 1] = A[i];
        --i;
    }

    A[i + 1] = key;
    
    insertion_sort_recursive(A, key_index + 1, array_size);
}

3. Merge Sort - Θ(nlg(n))
- pseudocode:

MERGE-SORT(A,p,r)
1 if p < r
2   q = [(p + r) / 2]
3   MERGE-SORT(A,p,q)
4   MERGE-SORT(A,q + 1, r)
5   MERGE(A, p, q, r)

MERGE(A,p,q,r)
1  n1 = q - p + 1
2  n2 = r - q 
3  let L[1.. n1 + 1] and R[1..n2 + 1] be new arrays
4  for i = 1 to n1
5   L[i] = A[p + i -1]
6  for j = 1 to n2
7   R[j] = A[q+ j]
8  L[n1 + 1] = INFINITY
9  R[n2 + 1] = INFINITY
10 i = 1
11 j = 1
12 for k = p to r
13  if L[i] <= R[j]
14      A[k] = L[i]
15      i = i + 1
16  else 
17      A[k] = R[j]
18      j = j + 1

C++ code (a little changed for better performance:

template<class T>
void merge_sort(vector<T>& A, int p, int r)
{
    if (p < r)
    {
        int mid = (p + r) / 2;
        merge_sort(A, p, mid);
        merge_sort(A, mid + 1, r);
        merge(A, p, mid, r);
    }
}

vector<int> one(SIZE);

template<class T>
void merge(vector<T>& A, int p, int q, int r)
{
    int i = p;
    int j = q + 1;
    int cursor = p;

    while (i <= q || j <= r)
    {
        if (i == q + 1)
        {
            one[cursor] = A[j];
            ++j;
        }
        else if (j == r + 1)
        {
            one[cursor] = A[i];
            ++i;
        }
        else if (A[i] <= A[j])
        {
            one[cursor] = A[i];
            ++i;
        }
        else
        {
            one[cursor] = A[j];
            ++j;
        }

        ++cursor;
    }

    for (int i = p; i <= r; ++i)
        A[i] = one[i];
}