1+ package Algorithms .sort ;
2+
3+ /********************************************************
4+ *
5+ * 08-722 Data Structures for Application Programmers
6+ * Lecture 14 Advanced Sorting
7+ *
8+ * Naive version of Merge Sort
9+ *
10+ *********************************************************/
11+ import java .util .Arrays ;
12+
13+ public class MergeSort {
14+
15+ private static final int SIZE =10000 ;
16+
17+ public static int []mergeSort (int []data ) {
18+ // parameter valid judge.
19+ if (data ==null ) {
20+ return null ;
21+ }
22+
23+ // the base case.
24+ int len =data .length ;
25+ if (len <=1 ) {
26+ return data ;
27+ }
28+
29+ // divide into two arrays.
30+ // create left half and right half.
31+ int left [] =new int [len /2 ];
32+ int right [] =new int [len -len /2 ];
33+
34+ System .arraycopy (data ,0 ,left ,0 ,len /2 );
35+ System .arraycopy (data ,len /2 ,right ,0 ,len -len /2 );
36+
37+ // call itself to sort left half
38+ left =mergeSort (left );
39+ right =mergeSort (right );
40+
41+ return merge (left ,right );
42+ }
43+
44+ // Precondition: two input arrays are sorted and they are not null.
45+ private static int []merge (int []left ,int []right ) {
46+ int len =left .length +right .length ;
47+
48+ int []ret =new int [len ];
49+
50+ int leftPoint =0 ;
51+ int rightPoint =0 ;
52+
53+ int cur =0 ;
54+ while (leftPoint <left .length &&rightPoint <right .length ) {
55+ if (left [leftPoint ] <right [rightPoint ]) {
56+ ret [cur ++] =left [leftPoint ++];
57+ }else {
58+ ret [cur ++] =right [rightPoint ++];
59+ }
60+ }
61+
62+ if (leftPoint >=left .length ) {
63+ while (rightPoint <right .length ) {
64+ ret [cur ++] =right [rightPoint ++];
65+ }
66+ }else {
67+ while (leftPoint <left .length ) {
68+ ret [cur ++] =left [leftPoint ++];
69+ }
70+ }
71+
72+ return ret ;
73+ }
74+
75+ public static void mergeSort2 (int []data ) {
76+ // parameter valid judge.
77+ if (data ==null ) {
78+ return null ;
79+ }
80+
81+ // the base case.
82+ int len =data .length ;
83+ if (len <=1 ) {
84+ return data ;
85+ }
86+
87+ // divide into two arrays.
88+ // create left half and right half.
89+ int left [] =new int [len /2 ];
90+ int right [] =new int [len -len /2 ];
91+
92+ System .arraycopy (data ,0 ,left ,0 ,len /2 );
93+ System .arraycopy (data ,len /2 ,right ,0 ,len -len /2 );
94+
95+ // call itself to sort left half
96+ left =mergeSort (left );
97+ right =mergeSort (right );
98+
99+ return merge (left ,right );
100+ }
101+
102+ public static void main (String []args ) {
103+ int []a =new int [SIZE ];
104+ for (int i =0 ;i <SIZE ;i ++)
105+ a [i ] = (int ) (Math .random () *SIZE );
106+
107+ //mergeSort(a);
108+
109+ int []test = {42 ,12 ,89 ,27 ,94 ,63 ,3 ,78 };
110+ System .out .println (Arrays .toString (mergeSort (test )));
111+
112+ // test merge method
113+ int []left = {12 ,42 ,63 ,89 };
114+ int []right = {3 ,27 ,78 ,94 };
115+ System .out .println (Arrays .toString (merge (left ,right )));
116+
117+ // test merge method
118+ int []left2 = {};
119+ int []right2 = {3 ,27 ,78 ,94 };
120+ System .out .println (Arrays .toString (merge (left2 ,right2 )));
121+ }
122+
123+ }