Iterative Merge Sort

1public void mergeSort(int[] arr) {
2    int n = arr.length;
3    int width = 1;
4
5    while (width < n) {
6        for (int left = 0; left < n; left += 2 * width) {
7            int mid = Math.min(left + width, n);
8            int right = Math.min(left + 2 * width, n);
9            merge(arr, left, mid, right);
10        }
11        width *= 2;
12    }
13}
14
15private void merge(int[] arr, int left, int mid, int right) {
16    int[] temp = new int[right - left];
17    int i = left, j = mid, k = 0;
18
19    while (i < mid && j < right) {
20        if (arr[i] <= arr[j]) {
21            temp[k++] = arr[i++];
22        } else {
23            temp[k++] = arr[j++];
24        }
25    }
26
27    while (i < mid) {
28        temp[k++] = arr[i++];
29    }
30
31    while (j < right) {
32        temp[k++] = arr[j++];
33    }
34
35    for (k = 0; k < temp.length; k++) {
36        arr[left + k] = temp[k];
37    }
38}