_{2}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: }`