Sorting Algorithm - Merge sort Implementation

The 4th sort algorithm I am going to show today is Merge Sort.

Merge sort

Merge Sort uses the Divide and Conquer algorithm because it involves splitting the array into sub-arrays.

There are two phases in Merge Sort: Splitting and Merging. We do the sorting during the merging phase.

The splitting phase is the preparation phase to make sorting faster during the merging phase.

Merge Sort

How does it work?

Splitting Phase

Start with an unsorted array, then we divide the array into 2 sub-arrays, and each sub-array we continue to divide into smaller arrays and so on. Until all the arrays only have one element (considered sorted)

Merging Phase

We take a bunch of one element arrays and then merging them into 2-element arrays, then 4–elements array and so on.

Start to merge from bottom to up. Merge the sibling arrays (left | right air). Each merge, making sure the resulting arrays are sorted. Until all arrays are merged into one, it means the array is sorted.

Implementation

Ascending

  • Initial a temporary array large enough to hold all elements in the arrays. E.g: first round, the temp array length equals 2

  • To merge sibling arrays left and right, we compare the value index from each array

    • i: first index of left array (not start from 0, the index of element getting from the orignial array)
    • j: first index of right array (not start from 0, the index of element getting from the original array)
    • if left[i] <= right[j] then copy left[i] into temp and increase i (i++)
    • if left[i] > right[j] then copy right[j] into temp and increase j (j++)
  • We compare to get the smallest value between left and right and copying it into temp array. Repeat until all elements in 2 arrays have been processed. It means the temp array now contains merged values in sorted order.

  • Then we copy the temp array back to original input array at the correct positions. Now the original array has changed - it contains few elements in sorted order.

  • We keep do it this until the original array contains all elements in sorted order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void asc_run(int[] arr) {
int startIndex = 0;
int endIndex = arr.length;

mergeSort(arr, startIndex, endIndex);

System.out.println("Ascending merge sort");
print(arr);
}

void mergeSort(int[] arr, int startIndex, int endIndex) {
// Break condition when length of sub array is 1
if (endIndex - startIndex < 2) {
return;
}

int midIndex = (startIndex + endIndex) / 2;

// Split the array into pair sub-arrays
// left side
mergeSort(arr, startIndex, midIndex);
// right side
mergeSort(arr, midIndex, endIndex);

// Merge pair sub-arrays together
merge(arr, startIndex, midIndex, endIndex);
}

void merge(int[] arr, int startIndex, int midIndex, int endIndex) {
// Break condition - both left-side and right-side are stored sub-array, hence if the largest element of left-side smaller than the smallest element of right-side, then return, no need to merge left and right into a sorted order
if (arr[midIndex - 1] <= arr[midIndex]) {
return;
}

int i = startIndex;
int j = midIndex;
int tempIndex = 0;
int[] tempArr = new int[endIndex - startIndex];

while (i < midIndex && j < endIndex) {
if (arr[i] <= arr[j]) {
// assign i to current position of tempIndex, then increment tempIndex and i
tempArr[tempIndex++] = arr[i++];
} else {
// assign j to current position of tempIndex, then increment tempIndex and j
tempArr[tempIndex++] = arr[j++];
}
}

// Copy the rest of elements in sub-arrays that haven't stay into tempArr
// if right-side sill have elements, then don't do because elements from right-side are greater than elements from left-side
// if left-side still have elements, then need to copy because the position maybe change
System.arraycopy(arr, i, arr, startIndex + tempIndex, midIndex - 1);

// copy tempArr to arr
System.arraycopy(tempArr, 0, arr, startIndex, tempIndex);
}