This site requires JavaScript, please enable it in your browser!
Greenfoot back
Abwatts
Abwatts wrote ...

2019/4/13

Problem with my Merge Sort Algorithm

Abwatts Abwatts

2019/4/13

#
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:
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();
        }
    }
Thanks!
nccb nccb

2019/4/14

#
One problem is that in your merge method, you are merging into finalList, but finalList is not returned from the method. I think you probably want to return finalList from merge, and then also add a return at the merge call in sort. Right now, you're passing in numList but numList is never modified and no sorted list is ever returned, so from the outside it appears as if nothing happens.
Abwatts Abwatts

2019/4/14

#
nccb wrote...
One problem is that in your merge method, you are merging into finalList, but finalList is not returned from the method. I think you probably want to return finalList from merge, and then also add a return at the merge call in sort. Right now, you're passing in numList but numList is never modified and no sorted list is ever returned, so from the outside it appears as if nothing happens.
Yes, you are right! I was able to find the problem and fix that. Thanks!
You need to login to post a reply.