How to do merge sort

Merge sort is a O(n*log₂n) complexity algorithm which is why it's preferred in various interviews. It is also a divide and conquer algorithm and the best way to sort linked lists, which I discussed in my previous post. The Java implementation of sorting collections (linked lists) is done using merge sort.

So here is how it's done. It's quite a lot of code, but it's easy to understand:

   1:  void mergeSort(int arr[], int first, int last) {

   2:      int SIZE = last - first;

   3:      if (SIZE <= 1)

   4:          return;

   5:      //if only 2 elements exist, just swap if necessary

   6:      if (SIZE == 2) {

   7:          if (arr[first] > arr[last - 1]) {

   8:              int tmp = arr[first];

   9:              arr[first] = arr[last - 1];

  10:              arr[last - 1] = tmp;

  11:          }

  12:          return;

  13:      }

  14:      //otherwise find the middle 

  15:      //and apply merge sort for each half

  16:      int half = first + SIZE / 2;

  17:   

  18:      mergeSort(arr, first, half);

  19:      mergeSort(arr, half, last);

  20:   

  21:      int i = first;

  22:      int j = half;

  23:      int* temp = new int[SIZE];

  24:      memset(temp, 0, sizeof(int) * SIZE);

  25:      int k = 0;

  26:      //after both halfs are sorted

  27:      //merge them together in one big sorted list

  28:      while (i < half || j < last) {

  29:          if (i < half && j < last) {

  30:              if (arr[i] < arr[j]) {

  31:                  temp[k] = arr[i];

  32:                  i++;

  33:              } else {

  34:                  temp[k] = arr[j];

  35:                  j++;

  36:              }

  37:          } else if (i < half) {

  38:              temp[k] = arr[i];

  39:              i++;

  40:          } else {

  41:              temp[k] = arr[j];

  42:              j++;

  43:          }

  44:          ++k;

  45:      }

  46:      //overrite the original array with the sorted elements

  47:      for (int m = 0; m < SIZE; m++)

  48:          arr[first + m] = temp[m];

  49:      delete[] temp;

  50:  }

How to do string matching

There are numerous algorithms for finding matches between strings and patterns, see wikipedia for detailed explanations. In the example implementation below, I chose a simpler variation of the Boyer-Moore algorithm, just because it's fast to implement and understand, and good enough in practice. The algorithm is called Boyer–Moore–Horspool algorithm or Horspool's algorithm.

It uses only the first table from Boyer-Moore, which is why it's easy to implement.
First, here's the function which build the table:

   1:  const int SIZE = 255;

   2:   

   3:  void computeTable(int arr[], char* pattern, int len) {

   4:      for (int i = 0; i < SIZE; i++) {

   5:          arr[i] = len;

   6:      }

   7:      for (int i = 0; i < len - 1; i++) {

   8:          arr[pattern[i]] = len - i - 1;

   9:      }

  10:  }

And the actual string matching uses the table which we build above:

   1:  int findOccurences(char* pattern, int patternLen, char* str, int strLen, int* table) {

   2:      int i = 0;

   3:      int pos = 0;

   4:      int last = patternLen - 1;

   5:      while (patternLen <= strLen) {

   6:          for (i = last; str[i] == pattern[i] && i >= 0; i--);

   7:          if (i == -1)

   8:              //return pos;

   9:              cout << "found one at position: " << pos << endl;

  10:          if (strLen <= table[str[last]])

  11:              return -1;

  12:          int offset = table[str[last]];

  13:          str += offset;

  14:          strLen -= offset;

  15:          pos += offset;

  16:      }

  17:      return -1;

  18:  }

You can use it simply by typing this:

   1:  int main() {

   2:      char pattern[] = "gcagagag";

   3:      char str[] = "gcatcgcagagagtatacagtacg";

   4:      int patternSize = sizeof(pattern) - 1;

   5:      int strSize = sizeof(str) - 1;

   6:      int arr[SIZE];

   7:      computeTable(arr, pattern, patternSize);

   8:      cout << "Finding occurences... " << endl;

   9:      cout << findOccurences(pattern, patternSize, str, strSize, arr) << endl;

  10:      return 0;

  11:  }

How to sort an array using heap sort

Heap-sort means using the heap structure and heap operations, as defined in my previous post, to sort a container such as an array. The complexity for heap sort is O(n * log₂n), explained next.

Take each element from the unsorted array and put it into a heap, restoring the heap property each time. Restoring the heap property is O(log₂ n) complexity and you have to multiply that for each element of the array, meaning O(n*log₂n). After you finish, remove one element at a time from the heap (the root each time, because it's the biggest element), restoring the heap property after each removal. Again, this is O(n*log₂n).

The full algorithm also requires O(n) additional space.
Here it is:

   1:  template <class T>

   2:  void sortArray(vector<T>* vec) {

   3:      vector<int>* heap = new vector<T>();

   4:      for (unsigned int i = 0; i < vec->size(); i++) {

   5:          addToHeap(heap, vec->at(i));

   6:      }

   7:      vec->clear();

   8:      T elem = deleteFromHeap(heap);

   9:      while (elem != -1) {

  10:          vec->push_back(elem);

  11:          elem = deleteFromHeap(heap);

  12:      }

  13:      delete heap;

  14:  }