Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Expand file tree

/

MergeSort.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
75 lines (67 loc) · 1.94 KB
/

MergeSort.java

Copy path

File metadata and controls

75 lines (67 loc) · 1.94 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
package src.main.java.com.sorts;
public class MergeSort {
/**
* This method implements the Generic Merge Sort
*
* @param unsorted the array which should be sorted
* @param <T> Comparable class
* @return sorted array
*/
@SuppressWarnings("unchecked")
public <T extends Comparable<T>> T[] sort(T[] unsorted) {
T[] tmp = (T[]) new Comparable[unsorted.length];
doSort(unsorted, tmp, 0, unsorted.length - 1);
return unsorted;
}
/**
* @param arr The array to be sorted
* @param temp The copy of the actual array
* @param left The first index of the array
* @param right The last index of the array
* Recursively sorts the array in increasing order
**/
private static <T extends Comparable<T>> void doSort(T[] arr, T[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
doSort(arr, temp, left, mid);
doSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
/**
* This method implements the merge step of the merge sort
*
* @param arr The array to be sorted
* @param temp The copy of the actual array
* @param left The first index of the array
* @param mid The middle index of the array
* @param right The last index of the array
* merges two parts of an array in increasing order
**/
private static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
System.arraycopy(arr, left, temp, left, right - left + 1);
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i].compareTo(temp[j]) <= 0) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
while (j <= right) {
arr[k] = temp[j];
j++;
k++;
}
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.