Sorting Algorithms

Insertion Sort

• Time: $O(N^2)$
• Space: $O(1)$

public void InsertionSort(int[] ar)
{
    for (int i = 1; i < ar.Length; i++)
    {
        int j = i;
        while (j > 0 && ar[j - 1] > ar[j])
        {
            int temp = ar[j];
            ar[j] = ar[j - 1];
            ar[j - 1] = temp;
            j--;
        }
    }
}

Merge Sort

• Time: $O(N \log N)$
• Space: $O(N)$

public void MergeSort(int[] ar)
{
    int[] tmp = new int[ar.Length];
    MergeSort(ar, tmp, 0, ar.Length - 1);
}

public void MergeSort(int[] ar, int[] tmp, int low, int high)
{
    if (low < high)
    {
        int mid = low + (high - low) / 2;
        MergeSort(ar, tmp, low, mid);
        MergeSort(ar, tmp, mid + 1, high);
        Merge(ar, tmp, low, mid, high);
    }
}

public void Merge(int[] ar, int[] tmp, int low, int mid, int high)
{
    int j = low, h = mid + 1;
    int k = low;
    while (j <= mid && h <= high)
    {
        if (ar[j] > ar[h])
            tmp[k++] = ar[h++];
        else tmp[k++] = ar[j++];
    }
    while (j <= mid)
    {
        tmp[k++] = ar[j++];
    }
    while (h <= high)
    {
        tmp[k++] = ar[h++];
    }
    for (int i = low; i <= high; i++)
    {
        ar[i] = tmp[i];
    }
}

Quick Sort

• Time: $O(N \log N)$ average, $O(N^2)$ worst case.
• Space: $O(\log N)$ stack space.

public void QuickSort(int[] ar, int left, int right)
{
    int pivot = ar[left + (right - left) / 2], i=left, j=right;
    while (i <= j)
    {
        while (ar[i]<pivot)
        {
            i++;
        }
        while (ar[j] > pivot)
        {
            j--;
        }
        if (i <= j)
        {
            int temp = ar[i];
            ar[i] = ar[j];
            ar[j] = temp;
            i++;
            j--;
        }
        if (i < right)
        {
            QuickSort(ar,i  ,right);
        }
        if (j > left)
        {
            QuickSort(ar,left,j);
        }
    }
}