-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathMergeSortAlgorithm.java
More file actions
79 lines (65 loc) · 2.04 KB
/
MergeSortAlgorithm.java
File metadata and controls
79 lines (65 loc) · 2.04 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
import java.util.*;
public class MergeSortAlgorithm
{
public static void main(String[] args)
{
Integer[] b = {2,4,6,7,9,1};
//Declare MergeSorting algorithm function first
MergeSortProcessor(b);
//check the sorts array and outputs it
System.out.println(Arrays.toString(b));
}
public static Comparable[] MergeSortProcessor(Comparable[] list)
{
//If list is empty, don't do anything.
//If list is empty, don't do anything.
if(list.length <= 1)
{
return list;
}
//Split the array in half in two parts
Comparable[] first = new Comparable[list.length / 2];
Comparable[] second = new Comparable[list.length - first.length];
System.arraycopy(list, 0, first, 0, first.length);
System.arraycopy(list, first.length, second, 0, second.length);
//Sorting each half recursively
MergeSortProcessor(first);
MergeSortProcessor(second);
//Merging both halfs together, overwriting to original array
merging(first, second, list);
return list;
}
private static void merging(Comparable[] first, Comparable[] second, Comparable[] result)
{
//indexing position in first array - starting with first element
int iFirst = 0;
//indexing position in second array - starting with first element
int iSecond = 0;
//indexing position in merged array - starting with first element
int iMerged = 0;
/*
* compare element at iFirst and iSecond,
* and move smaller element at iMerged
*/
while(iFirst < first.length && iSecond < second.length)
{
if(first[iFirst].compareTo(second[iSecond]) < 0)
{
result[iMerged] = first[iFirst];
iFirst++;
}
else
{
result[iMerged] = second[iSecond];
iSecond++;
}
iMerged++;
}
/*
* Copy the remaining elements from both halfs - each half will have
* already sorted elements.
*/
System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
}
}