Merge Sort

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

/** * * Simple merge sort * * Time Complexity: Worse case - O(nLogn) * Auxiliary Space: O(n) * Application: Used in External Sorting * * Note * - Merge sort is optimal with respect to # compares, * But not optimal with respect to space usage * * - Merge sort is generally considered better when data is huge and stored in external storage * * @author ramesh * */ public class Merge { private static final int ARRAY_DEFAULT_SIZE = 20; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); List<String> list = new ArrayList<String>(ARRAY_DEFAULT_SIZE); while (scanner.hasNext()) { String item = scanner.next(); if (item.equals("exit")) break; else { list.add(item); } } String ip_array[] = new String[list.size()]; for (int i = 0; i < ip_array.length; i++) { ip_array[i] = list.get(i); } sort(ip_array); for (int i = 0; i < ip_array.length; i++) { System.out.println(ip_array[i]); } scanner.close(); } private static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length-1); } private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi); } private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { for (int i = lo; i <= hi; i++) { aux[i] = a[i]; } int first_index = lo; int second_index = mid + 1; for (int i = lo; i <= hi; i++) { if (first_index > mid) { a[i] = aux[second_index++]; } else if (second_index > hi) { a[i] = aux[first_index++]; } else if (aux[first_index].compareTo(aux[second_index]) < 0) { a[i] = aux[first_index++]; } else { a[i] = aux[second_index++]; } } } }