Problem 1.
    a. O(N)
    b. O(N)
    c. O(N)
    d. O(N)
    e. O(1)
    f. O(N)
    g. O(logN)
    h. O(NlogN)
    i. O(N)
    j. O(N)

Problem 2.
void InsertionSort(dataType A[], int s, int N)
// Sorts the items in an array into ascending order by recursion.
// Precondition: the sorted region is A[0..s-1]
// Postcondition: the array A is sorted into ascending order.
{
    if (s<0 || s>=N) return;
    int Loc = s;
    dataType NextItem = A[Loc];
    while (Loc > 0 && A[Loc-1] > NextItem)
    {
        A[Loc] = A[Loc - 1];
        --Loc;
    }
    A[Loc] = NextItem;
    InsertionSort(A, s+1, N);
}

Problem 3.

In general, a sorting algorithm which compares two neighbor keys in the sorting process is stable. 

The stability is determined by the algorithm itself. For a unstable sorting algorithm, we can always find a unstable instance no matter how the algorithm is described. On the contrary, for a stable sorting algorithm, we can always find a description which will not lead to instability. 

Radix sort is stable, all simple sorting algorithms with O(N²) time complexity are stable, which include:
Selection Sort
Bubble sort
Insertion Sort
  
Problem 4. 

void Partition(dataType A[], int F, int L, int& PivotIndex)
{
    ChoosePivot(A, F, L);
    dataType pivot = A[F];
    int Low = F;
    int High = L;

    while (Low < High)
    {
        while (Low < High && A[High] >= pivot)
            --High;
        while (Low < High && A[Low] <= pivot)
            ++Low;
        if (Low < High)
        {
            Swap(A[Low], A[High]);
            ++Low;
            --High;
        }
    }
    Swap(A[F], A[High]);
    PivotIndex = High;
}

void QuickSort(dataType A[], int F, int L)
{
    int PivotIndex;
    if (F < L){
        Partition(A, F, L, PivotIndex);
        QuickSort(A, F, PivotIndex - 1);
        QuickSort(A, PivotIndex + 1, L);
    }
}

S1 and S2 not empty means the pivot can not be either the smallest one or the largest one in the current region. So each time make the pivot not to be the maximum or the minimum item in the region. But this makes the algorithm complicated. One simple and common method is to compare the first, the middle, and the last elements in the list and choose the median to be the pivot.