Merge Sort

The Algorithm

Merge Sort is a stable (preserve the order of equal elements), divide and conquer, comparison-based sorting algorithm. It has the worst-case run time of nlogn. The primary disadvantage of merge sort is usage of additional memory space.
The basic idea of merge sort is as below,

  • Divide the input array into sub arrays, each sub array contains 1 element.
  • Merge every two sub arrays into one sorted array. Repeat this process until there’s only one array left.

To ensure the merged array is sorted, we always compare the first element of the two sorted sub arrays and take the smaller one of the two. For example, we have an input array of “efdgabnm”. The merge process will be as below,
e        f        d        g        a         b      n         m
   ef                dg                 ab               mn
           defg                                  abmn
                           abdefgmn

There’re two common ways to implement merge sort. The first is called Top-down implementation, where recursion is used to divided the input array into sub arrays until each sub array contains 1 element and then merge them back. The second implementation is called Bottom-up implementation, where the input array is treated as an array of 1-element sub arrays. The algorithm merge the sub arrays iteratively between two buffers.

An Implementation in C

Below is the Top-down implementation of merge sort in C,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

void mergesort(int *base, int size, int **sorted) {

    int i, j;

    int *mp, *smp, *sbase;

    int *tmp;

    if (size <= 1) {

        if (size == 1) {

            *sorted = (int *)malloc(sizeof(int)*size);

            (*sorted)[0] = base[0];

        }

        return;

    }

    mp = base + size/2;

    mergesort(base, size/2, &sbase);

    mergesort(mp, size - size/2, &smp);

    printf("before merge:n");

    for (i = 0; i < size/2; ++i) {

        printf("%d ", sbase[i]);

    }

    printf("n");

    for (i = 0; i < size-size/2; ++i) {

        printf("%d ", smp[i]);

    }

    printf("n");

    tmp = (int *)malloc(sizeof(int)*size);

    for (i = 0, j = 0; i < size/2 && j < size-size/2; ) {

        if (sbase[i] < smp[j]) {

            tmp[i+j] = sbase[i];

            ++i;

        } else {

            tmp[i+j] = smp[j];

            ++j;

        }

    }

    for (; i < size/2; ++i) {

        tmp[i+j] = sbase[i];

    }

    for (; j < size-size/2; ++j) {

        tmp[i+j] = smp[j];

    }

    printf("after merge:n");

    for (i = 0; i < size; ++i) {

        printf("%d ", tmp[i]);

    }

    printf("n");

    free(smp);

    free(sbase);

    *sorted = tmp;

}

 

int main(int argc, char **argv) {

    int n;

    int i;

    int* testArray, *sorted;

    n = atoi(argv[1]);

    testArray = (int*)malloc(sizeof(int)*n);

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000;

    }

    printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");

    mergesort(testArray, n, &sorted);

    printf("nafter sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", sorted[i]);

    }

    printf("n");

}

Compile the code with the command below,

gcc -o ms mergesort.c

Here is a screenshot of a sample execution,

mergesort1

Figure 1. Execution of Top-down Implementation of Merge Sort

Below is the Bottom-up implementation of merge sort in C,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

int merge(int *a, int sa, int *b, int sb, int *res) {

    int i, j;

    for (i = 0, j = 0; i < sa && j < sb; ){

        if (a[i] < b[j]) {

            res[i+j] = a[i];

            ++i;

        } else {

            res[i+j] = b[j];

            ++j;

        }

    }

    for (; i < sa; ++i) {

        res[i+j] = a[i];

    }

    for (; j < sb; ++j) {

        res[i+j] = b[j];

    }

}

 

void mergesort(int *base, int size, int **sorted) {

    int i, j, k;

    int sa, sb;

    *sorted = (int*)malloc(sizeof(int)*size);

    if (size == 1) {

         (*sorted)[0] = base[0];

         return;

    }

    for (i = 1; i < size; i *= 2) {   //every round of merge size*2

        for (j = 0; j < size; j += 2*i) {

            sa = (j + i >= size)? (size - j):i;

            sa = (sa < 0) ? 0:sa;

            sb = (j + i + i >= size)?(size - (j + i)):i;

            sb = (sb < 0) ? 0:sb;

            merge(base + j, sa, base + j + i, sb, (*sorted) + j);

        }

        memcpy(base, *sorted, sizeof(int)*size);

        printf("i=%d;n", i, j);

        for (k = 0; k < size; ++k) {

            printf("%d ", base[k]);

        }

        printf("n");

    } 

}

 

int main(int argc, char **argv) {

    int n;

    int i;

    int* testArray, *sorted;

    n = atoi(argv[1]);

    testArray = (int*)malloc(sizeof(int)*n);

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000;

    }

    printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");

    mergesort(testArray, n, &sorted);

    printf("nafter sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", sorted[i]);

    }

    printf("n");

}

Compile the code with the command below,

gcc -o ms2 mergesort2.c

Here is a screenshot of a sample execution,

mergesort2

Figure 2. Execution of Bottom-up Implementation of Merge Sort

References:
1. Programming Perls. 2nd Edition.
2. Wikipedia Merge Sort: http://en.wikipedia.org/wiki/Merge_sort
3. Algorithms. 2.2 Mergesort. http://algs4.cs.princeton.edu/22mergesort/

Heapsort

You may want to read the previous post “heap” first.

Heapsort Algorithm

Heapsort is a in-place, not stable, worst-case nlogn sorting algorithm.

The simple implementation of heapsort is simply insert all elements into the heap and then remove the root repeatedly until the heap is empty. This is implemented in the code of post “heap” and “priority queue”.

However, this implementation consumes additional memory due of the usage of the heap/priority queue. Heapsort can actually be implemented using the input data array as the memory for building the heap. Therefore, heapsort is a in-place sorting algorithm.
The in-place version has two phases. Firstly we need to build a heap. This is done by dividing the input array as two parts, the first part contains the heapified data, and the second part contains other inputs. We loop through the input array, adds the current element to the heapified part at every iteration.

The second phase is to retrieve the element from the heap. Every time we remove the root element from the heap, the heap size is reduced by 1, so the space occupied by the last element before removal will be available for storing the removed element. (Essentially, we simply swap the first element and last element of the fully-heapifed array). We do this repeatedly until the heap is empty.

If we’re using a min binary heap, the input will be sorted into descending order as we’re repeatedly putting the smallest element from the heap to the end of the heapified part. If we want to sort the array into ascending order, we simply build a max binary heap. This is easy in code as we only need to change the value comparison from “<” to “>” or “>” to “<”.

C Implementation

Below we show an implementation of heapsort to sort a randomly generated array of integers to ascending order. The heap insert and remove functions are similar to the code in the post “heap”, except that the signs are changed to build a max binary heap instead of min binary heap.

#include <stdio.h>

#include <stdlib.h>

 

typedef struct heapData {

    //dummy

} heapData;

 

typedef struct heapNode {

    int value;

    heapData data;               //dummy

} heapNode;

 

void insert(heapNode aNode, heapNode* heap, int size) {

    int idx;

    heapNode tmp;

    idx = size + 1;

    heap[idx] = aNode;

    while (heap[idx].value > heap[idx/2].value && idx > 1) {         //change "<" to ">"

    tmp = heap[idx];

    heap[idx] = heap[idx/2];

    heap[idx/2] = tmp;

    idx /= 2;

    }

}

 

void shiftdown(heapNode* heap, int size, int idx) {

    int cidx;        //index for child

    heapNode tmp;

    for (;;) {

        cidx = idx*2;

        if (cidx > size) {

            break;   //it has no child

        }

        if (cidx < size) {

            if (heap[cidx].value < heap[cidx+1].value) {//change ">" to "<"

                ++cidx;

            }

        }

        //swap if necessary

        if (heap[cidx].value > heap[idx].value) {    //change "<" to ">"

            tmp = heap[cidx];

            heap[cidx] = heap[idx];

            heap[idx] = tmp;

            idx = cidx;

        } else {

            break;

        }

    }

}

 

heapNode removeMax(heapNode* heap, int size) {

    int cidx;

    heapNode rv = heap[1];

    //printf("%d:%d:%dn", size, heap[1].value, heap[size].value);

    heap[1] = heap[size];

    --size;

    shiftdown(heap, size, 1);

    return rv;

}

 

int main(int argc, char **argv) {

    int n; 

    int i;

    heapNode *heap;

    n = atoi(argv[1]);

    heap = (heapNode*)malloc(sizeof(heapNode)*(n+1));

    srand(time(NULL));

    for (i = 1; i <= n; ++i) {

        heap[i].value = rand()%10000;

    }

    printf("input:n");

    for (i = 1; i <= n; ++i) {

        printf("%d ", heap[i].value);

    }

    printf("nheapify:n");

    for (i = 2; i <=n ;++i) {

        insert(heap[i], heap, i-1);

    } 

    for (i = 1; i <= n; ++i) {

        printf("%d ", heap[i].value);

    }

    printf("nsort the heapified array:n");

    for (i = n; i > 0; --i) {

        heap[i] = removeMax(heap, i);        //use the end of the heapified part to store the removed element

    }

    for (i = 1; i <= n; ++i) {

        printf("%d ", heap[i].value);

    }

    printf("n");

}

Sample Execution

Compile the code using the command,

gcc -o hs heapsort.c

Below is a screenshot of the sample execution,

heapsort

Figure 1. Heapsort Sample Run

Run Time

Heapsort has worst-case nlogn run time, which is better than quicksort’s n^2 worst case run time. However, quicksort performs better than heapsort in practice at most cases.

Quick Sort and a Sample Implementation for C Standard Library qsort Function

Brief Notes of the Algorithm
Quicksort has an average run time of nlogn and worst case run time of n^2. Quicksort is often faster than other O(nlogn) algorithms in practice. And it’s used in implementation of C standard library qsort function.

Quicksort is not a stable sort, which means if two elements are equal, their order is not guaranteed to be preserved.

Quicksort is a divide and conquer algorithm. The basic idea of Quicksort is as follows,

  • pick up an element, called a pivot
  • reorder the list such that all elements that smaller than pivot is placed before the pivot, and the elements that bigger than pivot is placed after pivot. This operation is called partitioning. After partitioning, the pivot is at its final position.
  • recursively sort the sub-list that contains all the smaller elements and the sub-list contains all the bigger elements.
  • When a sub-list contains 0 or 1 element, there’s no need to parition.

C Implementation

The C standard library has a function “qsort” to sort an array. The function prototype is as below,

void qsort(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*));

qsort sorts n elements of array pointed by pointer base, where each element is size bytes long, using cmp function to determine the order. It arranges array in ascending order. sss
The function cmp must return negative value if first item is less than second, zero if equal and positive if greater.

Below is the first implementation of qsort,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

int intcmp(const void *a, const void *b) {

    return *(const int *)a - *(const int *)b;

}

 

void myswap(void *e1, void *e2, int size) {

    void* sp = (void*) malloc(size);

    memcpy(sp, e1, size);

    memcpy(e1, e2, size);

    memcpy(e2, sp, size);

    free(sp);

}

 

void myqsort(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {

    int i;

    int rv;

    void* mp;

    void* sp;  //for swap

 

    if (n <= 1) {return;}

    //printf("sort %d elementsn", n);

    mp = base;

    for (i = 1; i < n; ++i) {

        rv = cmp(base, base + size*i);

        if (rv > 0) {

            mp += size;

            if (mp != base+size*i) {

        //swap element at base+size*i with element at mp

        //printf("swap %d and %dn", *(int*)(base+size*i), *(int*)mp);

        myswap(base+size*i, mp, size);

            }

        }

    }

    //swap the base element with the element at mp

    myswap(base, mp, size);

    myqsort(base, (mp - base)/size, size, cmp);

    myqsort(mp + size, n - 1 - (mp-base)/size, size, cmp);

}

 

int main(int argc, char **argv) {

    int* testArray;

    int i;

    int n = atoi(argv[1]);

    struct timeval stTime, edTime;

    testArray = (int*) malloc(n*sizeof(int));

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000; 

    }

    /*printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    gettimeofday(&stTime, NULL);

    myqsort(testArray, n, sizeof(int), &intcmp);

    gettimeofday(&edTime, NULL);

    printf("%d: %u:%un", n, (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));

 

    /*printf("after sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    free(testArray);

    return 0;

}

The myqsort function always use the first element of a list/sub-list as the pivot. The pointer mp always points to the end of the sub-array with all elements smaller than pivot. If an element A is smaller than the pivot, then the pointer mp is incremented to pointing to a element B bigger than pivot, and A is swapped with B. After we scan through the entire array, we swap the pivot with the element pointed by mp.

The implementation has average run time of nlogn, however it cannot handle n equal elements efficiently (n^2). An alternative implementation is as below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

int intcmp(const void *a, const void *b) {

    return *(const int *)a - *(const int *)b;

}

 

void myswap(void *e1, void *e2, int size) {

    void* sp = (void*) malloc(size);

    memcpy(sp, e1, size);

    memcpy(e1, e2, size);

    memcpy(e2, sp, size);

    free(sp);

}

 

void myqsort2(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {

    int i, j;

 

    if (n <= 1) {return;}

   // printf("sort %d elementsn", n);

    i = 0; j = n;

    while (1) {

        do {

            ++i;

        } while(cmp(base + size*i, base) < 0 && i < n);

        do {

            --j;

        } while(cmp(base + size*j, base) > 0);   //no need to check j >= 0 because it will fail test when it reaches base

        if (i > j) break;

        myswap(base + size*i, base + size*j, size);

        //printf("%d:%dn", *(int*)(base+size*i), *(int*)(base+size*j));

    }

    //swap the base element with the j element

    if (j != 0) {

        myswap(base, base+size*j, size);

    }

    if (j > 0) {

        myqsort2(base, j, size, cmp);

    }

    myqsort2(base + size*(j+1), n - 1 - j, size, cmp);

}

 

int main(int argc, char **argv) {

    int* testArray;

    int i;

    int n = atoi(argv[1]);

    struct timeval stTime, edTime;

    testArray = (int*) malloc(n*sizeof(int));

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000; 

    }

    /*printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    gettimeofday(&stTime, NULL);

    myqsort2(testArray, n, sizeof(int), &intcmp);

    gettimeofday(&edTime, NULL);

    printf("%d: %u:%un", n, (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));

 

    /*printf("after sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    free(testArray);

    return 0;

}

The function myqsort2 uses two-sided partitioning code. The indices i and j are initialized to pointing to first element and last element of the array, and the first inner do-while loop goes from first element to the end of the array to check if the element it goes through are smaller than pivot, while the second inner do-while loop goes from the end to the beginning of the array to check if the element it goes through are bigger than pivot.

Every time the first inner loop encounters an element this is bigger than or equal to the pivot, it stops; every time the second inner loop encounters an element that is smaller than or equal to the pivot, it stops. Then we swap the two elements at i and j. When i and j are crossed over, the partition operation is done.

The second implementation can handle the n equal elements, but it still degrade to n^2 when the input n elements are already sorted. An alternative is to use a randomly picked element as pivot. This is implemented as below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

int intcmp(const void *a, const void *b) {

    return *(const int *)a - *(const int *)b;

}

 

void myswap(void *e1, void *e2, int size) {

    void* sp = (void*) malloc(size);

    memcpy(sp, e1, size);

    memcpy(e1, e2, size);

    memcpy(e2, sp, size);

    free(sp);

}

 

void myqsort3(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {

    int i, j;

    int ipos;

    if (n <= 1) {return;}

    ipos = rand()%n;

    myswap(base, base+ipos*size, size);

   // printf("sort %d elementsn", n);

    i = 0; j = n;

    while (1) {

        do {

            ++i;

        } while(cmp(base + size*i, base) < 0 && i < n);

        do {

            --j;

        } while(cmp(base + size*j, base) > 0);   //no need to check j >= 0 because it will fail test when it reaches base

        if (i > j) break;

        myswap(base + size*i, base + size*j, size);

        //printf("%d:%dn", *(int*)(base+size*i), *(int*)(base+size*j));

    }

    //swap the base element with the j element

    if (j != 0) {

        myswap(base, base+size*j, size);

    }

    if (j > 0) {

        myqsort3(base, j, size, cmp);

    }

    myqsort3(base + size*(j+1), n - 1 - j, size, cmp);

}

 

int main(int argc, char **argv) {

    int* testArray;

    int i;

    int n = atoi(argv[1]);

    struct timeval stTime, edTime;

    testArray = (int*) malloc(n*sizeof(int));

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000; 

    }

    /*printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    gettimeofday(&stTime, NULL);

    myqsort3(testArray, n, sizeof(int), &intcmp);

    gettimeofday(&edTime, NULL);

    printf("%d: %u:%un", n, (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));

 

    /*printf("after sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    free(testArray);

    return 0;

}

At begining of myqsort3, we swap the first element with a randomly picked element, and then use it as the pivot.

Quicksort is efficient when dealing with large arrays. If the array is small, quicksort’s recursive implementation may not perform better than other sorting algorithms like insertion sort. Insertion sort is efficient to sort an array that is almost sorted because the sequential memory access pattern.

To further improve the quick sort above, we first use quick sort to sort the array in a almost-sorted state, and then use insertion sort to sort the almost-sorted array. This is implemented as below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

unsigned int cutoff = 1;

 

int intcmp(const void *a, const void *b) {

    return *(const int *)a - *(const int *)b;

}

 

void myswap(void *e1, void *e2, int size) {

    void* sp = (void*) malloc(size);

    memcpy(sp, e1, size);

    memcpy(e1, e2, size);

    memcpy(e2, sp, size);

    free(sp);

}

 

void insersionSort(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {

   int i, j;

   void *tmp = (void*)malloc(size);

   for (i = 1; i < n; ++i) {

       memcpy(tmp, base + i*size, size);

       for (j = i-1; j >= 0 && cmp(tmp, base+j*size) < 0; --j) {

           memcpy(base+(j+1)*size, base+j*size, size);

       }

       memcpy(base+(j+1)*size, tmp, size);

   } 

}

 

void myqsort4(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {

    int i, j;

    int ipos;

    if (n <= cutoff) {return;}

    ipos = rand()%n;

    myswap(base, base+ipos*size, size);

   // printf("sort %d elementsn", n);

    i = 0; j = n;

    while (1) {

        do {

            ++i;

        } while(cmp(base + size*i, base) < 0 && i < n);

        do {

            --j;

        } while(cmp(base + size*j, base) > 0);   //no need to check j >= 0 because it will fail test when it reaches base

        if (i > j) break;

        myswap(base + size*i, base + size*j, size);

        //printf("%d:%dn", *(int*)(base+size*i), *(int*)(base+size*j));

    }

    //swap the base element with the j element

    if (j != 0) {

        myswap(base, base+size*j, size);

    }

    if (j > 0) {

        myqsort4(base, j, size, cmp);

    }

    myqsort4(base + size*(j+1), n - 1 - j, size, cmp);

}

 

int main(int argc, char **argv) {

    int* testArray;

    int i;

    int n = atoi(argv[1]);

    cutoff = atoi(argv[2]);

    struct timeval stTime, edTime;

    testArray = (int*) malloc(n*sizeof(int));

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000; 

    }

    /*printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    gettimeofday(&stTime, NULL);

    myqsort4(testArray, n, sizeof(int), &intcmp);

 

    /*printf("after sort 1:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    insersionSort(testArray, n, sizeof(int), &intcmp);

    gettimeofday(&edTime, NULL);

    printf("%d: %u:%un", n, (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));

 

    /*printf("after sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    free(testArray);

    return 0;

}

The program accepts an additional input parameter “cutoff” to stop the qsort when the sub-array is short.

To compare the performance of our implementations with the C standard library implementation, an implementation using C standard library qsort function is as below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

int intcmp(const void *a, const void *b) {

    return *(const int *)a - *(const int *)b;

}

 

int main(int argc, char **argv) {

    int* testArray;

    int i;

    int n = atoi(argv[1]);

    struct timeval stTime, edTime;

    testArray = (int*) malloc(n*sizeof(int));

    srand(time(NULL));

    for (i = 0; i < n; ++i) {

        testArray[i] = rand()%1000; 

    }

    /*printf("before sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    gettimeofday(&stTime, NULL);

    qsort(testArray, n, sizeof(int), &intcmp);

    gettimeofday(&edTime, NULL);

    printf("%d: %u:%un", n, (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));

 

    /*printf("after sort:n");

    for (i = 0; i < n; ++i) {

        printf("%d ", testArray[i]);

    }

    printf("n");*/

 

    free(testArray);

    return 0;

}

Sample Execution

Sample execution of the above programs are as below (suppose the five programs are compiled as qs1, qs2, qs3, qs4, and qs5 respectively),

1

The C standard library qsort is highly optimized and outperforms the implementations above.

References:

Programming Perls, second edition

Million Integer Problems — Part 2. Sorting a Million Integers

This is the second post for million integer problems. The first post is about generating million integers. You can find it here. This post deals with sorting of million integers.

It can be proven that the best that a comparison-based sorting can do has average run time of nlogn. However, given specific inputs, there’re algorithms that can do better than nlogn. The million integer sorting is one of such cases.

1. Sorting a million integers in the range of [0, 1 000 000]. Numbers can appear many times.

Since the comparison-based sorting algorithms can only do nlogn, we’ll see if we can sort without compare the one million elements.

The inputs are all integers, and it’s within a specific range [0, 1 000 000]. Integers can be the index of arrays. If we have an array with 1 million indices, every time an input appears, we mark the element in the array. If an integer appear N times, we mark the array element N times.

After reading all inputs, the indices corresponding to all input integers are marked. Because indices are ordered, we simply read from array element 0 to 1 million, if the array element is marked as N, we output the index N times.

The C implementation is as below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

#define MAXV 1000000

 

unsigned int buckets[MAXV+1];

 

int main(int argc, char **argv) {

   FILE* inputF, *outputF;

   int i;

   char aline[15];

   inputF = fopen("input1.txt", "r");

   if (inputF == NULL) {

       printf("cannot open input filen");

       return 0;

   }

   memset(buckets, 0x00, MAXV+1);

   while (fgets(aline, 15, inputF) != NULL) {

       i = atoi(aline);

//       printf("...%dn", i);

       ++buckets[i];

   }

   outputF = fopen("output1.txt", "w");

   for (i = 0; i <= MAXV; ++i) {

       while (buckets[i]--) {

           fprintf(outputF, "%dn", i);

       }

   }

   fclose(inputF);

   fclose(outputF);

}

You can use the code in part 1 generate 1 million integers to generate the input files for the above code.

2. Sorting a million integers in the range of [0, 1 000 000]. No number appears twice.

Compare with first problem, there’s one additional condition, the input integers are unique. This means the array element we used in first problem has either value 0 or 1. A single bit is enough to represent the array element.

The C implementation is as below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

#define MAXV 1000000

 

unsigned char buckets[(MAXV+7)/8];

 

void setb(int i) {

    int idx = i/8;

    int bpos = i%8;

    buckets[idx] |= (0x01 << bpos);

}

 

int checkb(int i) {

    int idx = i/8;

    int bpos = i%8;

    return (buckets[idx] & (0x01 << bpos));

}

 

int main(int argc, char **argv) {

   FILE* inputF, *outputF;

   int i;

   char aline[15];

   inputF = fopen("input.txt", "r");

   if (inputF == NULL) {

       printf("cannot open input filen");

       return 0;

   }

   memset(buckets, 0x00, (MAXV+7)/8);

   while (fgets(aline, 15, inputF) != NULL) {

       i = atoi(aline);

//       printf("...%dn", i);

       setb(i);

   }

   outputF = fopen("output.txt", "w");

   for (i = 0; i <= MAXV; ++i) {

       if (checkb(i)) {

           fprintf(outputF, "%dn", i);

       }

   }

   fclose(inputF);

   fclose(outputF);

}

You can use the code in part 1 generate 1 million integers to generate the input files for the above code.

2.1 Implementation from Programming Perls

The classic book Programming Perls has a implementation that sorts the input integers. The code is as below,

/* Copyright (C) 1999 Lucent Technologies */

/* From 'Programming Pearls' by Jon Bentley */

 

/* bitsort.c -- bitmap sort from Column 1

 *   Sort distinct integers in the range [0..N-1]

 */

 

#include <stdio.h>

 

#define BITSPERWORD 32

#define SHIFT 5

#define MASK 0x1F

#define N 10000000

int a[1 + N/BITSPERWORD];

 

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }

void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }

int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

 

int main()

{    int i;

    for (i = 0; i < N; i++)

        clr(i);

/*    Replace above 2 lines with below 3 for word-parallel init

    int top = 1 + N/BITSPERWORD;

    for (i = 0; i < top; i++)

        a[i] = 0;

 */

    while (scanf("%d", &i) != EOF)

        set(i);

    for (i = 0; i < N; i++)

        if (test(i))

            printf("%dn", i);

    return 0;

}

3. Related problems
3.1 There are 1 000 001 integers in the range of [0, 1 000 000]. Given a million unique integers in the range of [0, 1 000 000], find the integer that is missing.

This is actually the same as integer sorting problems. Once you sort the integers with the array, you can iterate through the array to find the array index whose element is not marked.

There are other problems. If you happens to encounter one, you’re welcome to add it in the comments. 🙂

References

1. Programming Perls. Second Edition.

2. Programming Perls Source Code website: http://www.cs.bell-labs.com/cm/cs/pearls/code.html

Some Sorting Algorithms

Side Note: I found this on my computer. I wrote this some time in 2009. Just to put everything to a single place.

Insertion sort:
Basic Idea:

        1. starting from index 1, going through the array and every iteration insert the current element into a proper position at the already sorted previous positions.
        2. The reason the outer loop starts from 1 instead of 0 is that the first element is considered sorted itself.

Source code in C++

#include <iostream>
using namespace std;

class InsertionSort {
  public:
    static void insertionSort(int * a, int n) {
        int i, j, t;
        for (i = 1; i < n; ++i) {
        j = i;
            t = a[i];
            while (j > 0 && a[j-1] > t) {
            a[j] = a[j-1];
                --j;
        }
            a[j] = t;
    }
    }   
}; int main() {
    int test[5] = {2, 3, 8, 4, 7};
    InsertionSort::insertionSort(test, 5);
    for (int i = 0; i < 5; ++i) {
        cout << test[i] << endl;
    }
    return 0;
}

   
Selection Sort:

Basic Ideas:

        1. Starting from index 0, going through the entire array, every time select the smallest element from the unsorted part and swap it with the current element.

Source code in C++:


#include <iostream>

using namespace std;

class SelectionSorter {

  public:

    static void selectionSort(int *a, int n) {

        int i, j, k, t;

        for (i = 0; i < n; ++i) {

        t = a[i];

        k = i;

        for (j = i+1; j < n; ++j) {

            if (a[j] < t) {

           t = a[j];

           k = j;

        }

        }

        a[k] = a[i];

        a[i] = t;

    }

    }

};

int main() {

    int test[5] = {3, 4, 2, 5, 8};

    SelectionSorter::selectionSort(test, 5);

    for (int i = 0; i < 5; ++i) {

        cout << test[i] << endl;

    }

    system("pause");

    return 0;

}

Bubble sort: 

Basic Ideas:

        1. It starts from index 0, by swapping the neighboring elements if they’re not in order. At every iteration, one element is put to the right position at the tail of the array.

Source code in C++:


#include <iostream>

using namespace std;

class BubbleSorter {

  public:

    static void bubbleSort(int *a, int n) {

        int i, j, t;

        for (i = 0; i < n; ++i) {

        for (j = 1; j < n-i; ++j) {

            if (a[j-1] > a[j]) {

           t = a[j-1];

           a[j-1] = a[j];

           a[j] = t;

        }

        }

    }

    }

};

int main() {

    int test[5] = {2, 3, 8, 4, 7};

    BubbleSort::bubbleSort(test, 5);

    for (int i = 0; i < 5; ++i) {

        cout << test[i] << endl;

    }

    system("pause");

    return 0;

}