-
Notifications
You must be signed in to change notification settings - Fork 13
/
SortArrayMergeSort912.java
35 lines (34 loc) · 1010 Bytes
/
SortArrayMergeSort912.java
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
package Leetcode;
public class SortArrayMergeSort912 {
/** Method6: Merge Sort; Average Time: O(NlogN), The Best Time: O(NlogN), The Worst Time: O(NlogN); Space: O(1) Stability: true **/
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length-1);
return nums;
}
private void mergeSort(int[] a, int start, int end) {
if(a == null || start >= end) { return; }
int mid = (start + end) /2;
mergeSort(a, start, mid);
mergeSort(a, mid + 1, end);
merge(a, start, mid, end);
}
private void merge(int[] a, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid +1;
int k =0;
while(i <= mid && j <= end) {
if(a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while(i<=mid) { temp[k++] = a[i++]; }
while(j <= end) { temp[k++] = a[j++]; }
for(i = 0; i < k; i++) {
a[start + i] = temp[i];
}
temp=null;
}
}