Welcome Message

Hi, welcome to my website. This is a place where you can get all the questions, puzzles, algorithms asked in interviews and their solutions. Feel free to contact me if you have any queries / suggestions and please leave your valuable comments.. Thanks for visiting -Pragya.

January 2, 2010

Complete + Easy + My MergeSort

public class MyMergeSort {

/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 14, 23, 76, 32, 76, 12, 11, 90 };
mergeSort(arr , 0 ,arr.length);
for(int i = 0 ; i < arr.length ; i ++){
System.out.println(arr[i]);
}
}

public static void mergeSort(int[] input , int firstIndex , int lastIndex){
int leftHalfSize;
int rightHalfSize;
if(lastIndex > 1){
leftHalfSize = lastIndex / 2;
rightHalfSize = lastIndex - leftHalfSize;

mergeSort(input, firstIndex, leftHalfSize);
mergeSort(input, firstIndex + leftHalfSize, rightHalfSize);

merge(input , firstIndex , leftHalfSize , rightHalfSize);
}

}
public static void merge(int[] input , int firstIndex , int leftHalfSize , int rightHalfSize){
int[] temp = new int[leftHalfSize + rightHalfSize];

int[] leftArray = new int[leftHalfSize];
int[] rightArray = new int[rightHalfSize];

for(int i = 0 ; i < leftHalfSize ; i++){
leftArray[i] = input[firstIndex + i];
}
for(int j = 0 ; j < rightHalfSize ; j++){
rightArray[j] = input[firstIndex + leftHalfSize + j ];
}
int i = 0 , j = 0 ,k = 0;
for(; i < leftHalfSize && j < rightHalfSize ;){
if(leftArray[i] < rightArray[j]){
temp[k] = leftArray[i];
i++;
k++;
}else{
temp[k] = rightArray[j];
j++;
k++;
}
}
if(i < leftHalfSize){
while (i < leftHalfSize || k < leftHalfSize + rightHalfSize){
temp[k] = leftArray[i];
k++;
i++;
}
}

if(j < rightHalfSize){
while (j < rightHalfSize || k < leftHalfSize + rightHalfSize){
temp[k] = rightArray[j];
k++;
j++;
}
}
for(int m = 0 ; m < leftHalfSize + rightHalfSize ; m++){
input[firstIndex+ m ] = temp[m] ;
}
}

}

No comments: