I have tried implementing the merge sort algorithm using lists. The problem is that not the entire list is getting sorted, but only a couple of terms. I don't really understand what might be the problem with my code... Could someone please help?
Here's the code:
Thanks!
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 91 | public static void sort(List<Integer> numList, int n) { boolean debug = false ; n = numList.size(); // here the recursion occurs if (n <= 1 ) { // containing one element in list if (debug) { for ( int i = 0 ; i < n; i++) { System.out.println( "Containing one element: " + numList.get(i) + " " ); } } System.out.println(); return ; } int midPt = (numList.size() / 2 ); List<Integer> leftList = new ArrayList(); List<Integer> rightList = new ArrayList(); if (debug) { System.out.println( "Original List:\n" + numList); } // populating the left list for ( int i = 0 ; i < midPt; i++) { leftList.add(numList.get(i)); if (debug) { System.out.print(leftList.get(i) + " " ); } } if (debug) { System.out.println(); } // populating the right list for ( int i = n - 1 ; i >= midPt; i--) { rightList.add(numList.get(i)); if (debug) { System.out.print(numList.get(i) + " " ); } } if (debug) { System.out.println(); } // recursion occurs until each list contains only 1 element sort(leftList, leftList.size()); sort(rightList, rightList.size()); // merging all the lists containing 1 element in them merge(rightList, leftList); } public static void merge(List<Integer> rightList, List<Integer> leftList) { List<Integer> finalList = new ArrayList(); int rightIndex = 0 ; int leftIndex = 0 ; int finalIndex = 0 ; // while there are terms in either list while (rightIndex < rightList.size() && leftIndex < leftList.size()) { // if there are elements in both lists at the same time System.out.println( "leftList: " + leftList); System.out.println( "rightList: " + rightList); // if the right term is smaller than the left term (rightList) if (rightList.get(rightIndex) >= leftList.get(leftIndex)) { finalList.add(finalIndex++, leftList.get(leftIndex++)); } else { finalList.add(finalIndex++, rightList.get(rightIndex++)); } // while the right index is less than the total terms in the list(only elemnts in the right list) while (rightIndex < rightList.size()) { finalList.add(finalIndex++, rightList.get(rightIndex++)); } //finalList.add(finalIndex++, rightList.get(rightIndex++)); while (leftIndex < leftList.size()) { finalList.add(finalIndex++, leftList.get(leftIndex++)); } for ( int i = 0 ; i < finalList.size(); i++) { System.out.print(finalList.get(i) + " " ); } System.out.println(); } } |