Created
March 14, 2017 07:59
-
-
Save devteampentagon/9542634fe4b355f44c6073281dce14ab to your computer and use it in GitHub Desktop.
Merge Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package kumar116; | |
| public class Mergesort <T extends Comparable<T>> { | |
| public void sort(T[] data) { | |
| mergesort(data, 0, data.length - 1); | |
| } | |
| private void mergesort(T[] data, int low, int high) { | |
| if (low < high) { | |
| int middle = low + (high - low) / 2; | |
| mergesort(data, low, middle); | |
| mergesort(data, middle + 1, high); | |
| merge(data, low, middle, high); | |
| } | |
| } | |
| private void merge(T[] data, int low, int middle, int high) { | |
| Object[] dataCopy = new Object[data.length]; | |
| for (int i = low; i <= high; i++) { | |
| dataCopy[i] = data[i]; | |
| } | |
| int i, k; | |
| i = k = low; | |
| int j = middle + 1; | |
| while (i <= middle && j <= high) { | |
| if (((T)dataCopy[i]).compareTo((T)dataCopy[j]) <= 0) { | |
| data[k] = (T)dataCopy[i]; | |
| i++; | |
| } else { | |
| data[k] = (T)dataCopy[j]; | |
| j++; | |
| } | |
| k++; | |
| } | |
| while (i <= middle) { | |
| data[k] = (T)dataCopy[i]; | |
| k++; | |
| i++; | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Mergesort mergeSort = new Mergesort(); | |
| Integer[] data = {1, 9, 2, 8, 4, 7, 6, 5}; | |
| mergeSort.sort(data); | |
| for (int i = 0; i < data.length; i++) { | |
| System.out.print(data[i].toString() + "\t"); | |
| } | |
| System.out.println(); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment