-
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathVersion2_MergeSort.java
More file actions
108 lines (79 loc) · 2.69 KB
/
Copy pathVersion2_MergeSort.java
File metadata and controls
108 lines (79 loc) · 2.69 KB
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package Sorting;
import java.util.Arrays;
// version two still uses an extra array to merge but reduces the smaller array created while sorting
/*
BREAK → SORT → MERGE
BREAK the array into halves until one element remains.
SORT happens automatically because a single element is already sorted.
MERGE the small sorted pieces back together.
And for the merge step:
COMPARE → PICK SMALLER → MOVE POINTER
Repeat until one side finishes, then:
COPY THE LEFTOVERS
*/
public class Version2_MergeSort {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
// Sort the entire array.
mergeSortInPlace(arr, 0, arr.length);
System.out.println(Arrays.toString(arr));
}
static void mergeSortInPlace(int[] arr, int s, int e) {
// If only one element is present,
// it is already sorted.
if (e - s == 1)
return;
// Split the current portion into two halves.
int mid = (s + e) / 2;
// Sort the left half.
mergeSortInPlace(arr, s, mid);
// Sort the right half.
mergeSortInPlace(arr, mid, e);
// Both halves are now sorted.
// Merge them into one sorted portion.
mergeInPlace(arr, s, mid, e);
}
static void mergeInPlace(int[] arr, int s, int m, int e) {
// Temporary array used to store the merged result.
// Size = total elements between s and e.
int[] mix = new int[e - s];
// i -> current element in left half
// j -> current element in right half
// k -> current position in mix array
int i = s;
int j = m;
int k = 0;
// Keep comparing until one half gets exhausted.
while (i < m && j < e) {
// Pick the smaller element and put it into mix.
if (arr[i] < arr[j]) {
mix[k] = arr[i];
i++; // move left pointer
} else {
mix[k] = arr[j];
j++; // move right pointer
}
// Move to next position in mix.
k++;
}
// If elements are still left in the left half,
// copy them directly.
while (i < m) {
mix[k] = arr[i];
i++;
k++;
}
// If elements are still left in the right half,
// copy them directly.
while (j < e) {
mix[k] = arr[j];
j++;
k++;
}
// Copy the sorted data back into the original array.
// Start writing from index 's'.
for (int l = 0; l < mix.length; l++) {
arr[s + l] = mix[l];
}
}
}