#include<stdio.h> /* * Implemented by Arjun Sunel. */ // Merging the sorted left and right subarrays. void Merge(int array[], int startIndex, int midIndex, int endIndex) { int leftSubArraySize = (midIndex - startIndex) + 1 ; int rightSubArraySize = (endIndex - midIndex); int Left[leftSubArraySize], Right[rightSubArraySize]; int i, j, k; for( i = 0; i < leftSubArraySize; i++) { Left[i] = array[startIndex + i]; } for( j = 0; j < leftSubArraySize; j++) { Right[j] = array[midIndex + j + 1]; } i = 0; j = 0; k = startIndex; while(i < leftSubArraySize && j < rightSubArraySize) { if(Left[i] <= Right[j]) { array[k] = Left[i]; i++; } else { array[k] = Right[j]; j++; } k++; } while(i < leftSubArraySize) { array[k] = Left[i]; i++; k++; } while(j < rightSubArraySize) { array[k] = Right[j]; j++; k++; } } // MergeSort method void MergeSort(int array[], int startIndex, int endIndex) { if(startIndex < endIndex) { int midIndex = (startIndex + (endIndex - startIndex)/2); // recursively call the MergeSort method on the left and right subarrays. MergeSort(array, startIndex, midIndex); MergeSort(array, midIndex + 1, endIndex); Merge(array, startIndex, midIndex, endIndex); } } // Entry point of the program int main() { int array[] = {5, -12, 14, 7}; int arraySize = 4; int index; printf("Before sorting : \n"); for(index = 0; index <= arraySize - 1; index++) { printf("%d ", array[index]); } MergeSort(array, 0, arraySize-1); printf("\nAfter sorting : \n"); for(index = 0; index <= arraySize - 1; index++) { printf("%d ", array[index]); } printf("\n"); }
Sunday, 14 December 2014
Recursive MergeSort for Array of Integers
Labels:
Sorting
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment