マージソート

何となく作りたくなったので，マージソート．

■コード

view plainprint?

1. /** Marge sort(マージソート) */  
2. public void margeSort(int[] a){  
3.  int n=a.length;  
4.  if(n==1) return;  
5.  // b.length+c.length=a.length  
6.  int[] b=new int[n/2];  
7.  int[] c=new int[n-n/2];  
8.  System.arraycopy(a, 0, b, 0, b.length);  
9.  System.arraycopy(a, n/2, c, 0, c.length);  
10.  margeSort(b);  
11.  margeSort(c);  
12.  // ソートされたbとcをaにマージ  
13.  for(int i=0, j=0, k=0;i<n;i++)  
14.   if(k==c.length)  
15.    a[i]=b[j++];  
16.   else if(j==b.length)  
17.    a[i]=c[k++];  
18.   else if(b[j]<c[k])  
19.    a[i]=b[j++];  
20.   else  
21.    a[i]=c[k++];  
22. }  

/** Marge sort(マージソート) */
public void margeSort(int[] a){
 int n=a.length;
 if(n==1) return;
 // b.length+c.length=a.length
 int[] b=new int[n/2];
 int[] c=new int[n-n/2];
 System.arraycopy(a, 0, b, 0, b.length);
 System.arraycopy(a, n/2, c, 0, c.length);
 margeSort(b);
 margeSort(c);
 // ソートされたbとcをaにマージ
 for(int i=0, j=0, k=0;i<n;i++)
  if(k==c.length)
   a[i]=b[j++];
  else if(j==b.length)
   a[i]=c[k++];
  else if(b[j]<c[k])
   a[i]=b[j++];
  else
   a[i]=c[k++];
}

■特徴
・分割統治法を用いたソートアルゴリズム
・最悪計算量O(nlogn)
・安定ソートである

■原理
ある配列(数列)aとbが以下であるとします．

a1, …, am

b1, …, bn

この時，

ai<=ai+1

bj<=bj+1

とすれば，つまり，aもbもソートされているとすれば，それらをマージした以下の配列(数列)cが作れる．

c1, …, cm+n

これを再帰的に適用します．

■適用例
8,3,4,6,2,5,7,1

まずは，"分割"します．

8

3

4

6

2

5

7

1

8

3

4

6

2

5

7

1

8

3

4

6

2

5

7

1

8

3

4

6

2

5

7

1

配列の要素が一つになるまで"分割"しました．要素数が1の配列が"ソートされている事"は，明らかですので，ここからはソートされている配列を"統治"していきます．

3

8

4

6

2

5

1

7

ここで，要素数が2の配列が4つ出来ましたが，それぞれソートされています．

3

4

6

8

1

2

5

7

1

2

3

4

5

6

7

8

というわけでゴール．正しくソートされました．