Skip to content

Instantly share code, notes, and snippets.

@unsign3d
Created March 15, 2013 17:43
Show Gist options
  • Save unsign3d/5171668 to your computer and use it in GitHub Desktop.
Save unsign3d/5171668 to your computer and use it in GitHub Desktop.
recursive merge sort in java, just for study
import java.util.Arrays;
public class MergeSort{
public static void main(String[] args) {
int a[]= { 5, 7, 2, 8, 11, 34, 2, 0, 7};
System.out.println("Prima: "+Arrays.toString(a)+"\n");
merge_sort(a);
System.out.println("Dopo: "+Arrays.toString(a));
}
public static void merge_sort(int[] a, int[] b, int left, int right){
int mid;
if(left < right){
//trovo la meta'
mid = (left + right) / 2;
//applico la ricorsione e spezzo in 2 l'array
merge_sort(a, b, left, mid);
merge_sort(a, b, mid+1, right);
//rimetto assieme gli array
merge(a, b, left, mid+1, right);
}
}
public static void merge_sort(int[] a){
int[] b = new int[a.length];
merge_sort(a, b, 0, a.length -1);
}
public static void merge(int a[], int b[], int left, int center, int right){
int end1 = center -1; //indice di dove finisce il primo array
int j = left; //da dove parto con b
int n = right - left + 1; //numero di elementi
//scansione array
while(left <= end1 && center <= right){
//copio il minore nella prima posizione libera di b
if(a[left] <= a[center]){
b[j++] = a[left++];
} else {
b[j++] = a[center++];
}
}
//fondo la prima parte
while(left <= end1 ){
b[j++] = a[left++];
}
while(center <= right){
b[j++] = a[center++];
}
//copio l'array
for (int i= 0; i < n; i++, right--){
a[right] = b[right];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment