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:  }