# Merge Sort

source code

## Java Code

Warning: Only the algorithm is displayed on this page.
Download the source code for a compilable/runnable test, or go here for the complete library of sorting algorithms.

##### MergeSort.java
```package sorts;

/**
* MergeSort.java
* Created by Stijn Strickx on May 21, 2008
*/

/**
* Merge sort algorithm
* Average Time Complexity: O(n log n)
* Worst Time Complexity: O(n log n)
* Memory Complexity: O(n)
* Stable: yes
*/

public class MergeSort extends Sorter{

@Override
public <T extends Comparable<? super T>> void sort(T[] a) {
// Generic array creation is not possible! (grr)
Comparable[] b = new Comparable[a.length];
sort(a,b,0,a.length-1);
}

private <T extends Comparable<? super T>> void sort(T[] a, T[] b, int low, int high) {
if(low < high){
int middle = (low+high) / 2;
sort(a,b,low,middle);
sort(a,b,middle+1,high);
int s_high = middle+1;
int s_low = low;
for(int i = low; i <= high; i++){
if((s_low <= middle) && ((s_high > high) || (a[s_low].compareTo(a[s_high]) < 0)))
b[i] = a[s_low++];
else
b[i] = a[s_high++];
}
for(int i = low; i <= high; i++)
a[i] = b[i];
}
}
}
```

### Most Popular Lessons

Home | Code | Learn
© 2007-2008 ProgLogic, all rights reserved. | ProgLogic.com is created by Stijn Strickx. | e-mail