Sorting Algorithms

MERGE SORT

Divide and conquer a gore calisir. Ortadan ikiye boler. Her iki tarafi da kendi icinde siralar. Taa ki tek eleman kalana kadar. En son bu siralananlari birlestirip yeniden siralar.

 4 7 | 6 8 5 icin ortadan ayirir.

4 7 | 5 6 8

4 5 6 7 8 seklinde doner.

Time Complexity : O(nlog(n))

Kod

public static void mergeSort(int a[], int n) {
 if(n < 2) return ; 
 int mid = n/2;
 int left[] = new int[mid];
 int right[] = new int[n - mid];
  
 for(int i=0; i < mid; i++) {
  left[i] = a[i];
 }
 for(int i=mid; i< n;i++) {
  right[i -mid]= a[i]; 
 }
 mergeSort(left, mid);
 mergeSort(right, n-mid);
 merge(a, left,right,mid,n-mid);
}