Merge Sort in String using LinkedList

Question

I used LinkedList as a dymanic array then this array contains strings that need to be sorted in alphabetical order by using merge sort algorithm, which is added in the method and it turned out not working. Any suggestions?

public static LinkedList<String> merge(LinkedList<String> linkedList, LinkedList<String> linkedList2) {
        LinkedList<String> result = new LinkedList<String>();
        if(linkedList.size() == 0)
            result.add(linkedList2.remove());
        else if (linkedList2.size() == 0)
            result.add(linkedList.remove());

        for(int i=0; i<linkedList.size(); i++) {
            if(linkedList.get(i).compareTo(linkedList2.get(i)) < 0)
                result = linkedList;
            else
                result = linkedList2;
        }

        return result;
    }

zw324 · Accepted Answer · 2013-05-19 14:08:43Z

1

The logic is wrong here, see comments for right logic:

    while(0 < linkedList.size() || 0 < linkedList2.size())
        if(0 == linkedList.size())        // if linkedList is empty
            result.add(linkedList.remove());        // should add head of linkedlist2 to result
        else if (0 == linkedList2.size())        // vice
            result.add(linkedList2.remove());       // versa
        else {
            linkedList.get(0).compareTo(linkedList2.get(0));      // else add the smaller of the two; you are just comparing, not adding the smaller
        }

answered May 19, 2013 at 14:08

zw324

27.2k16 gold badges88 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

zw324 Over a year ago

Your loop was fine, but the logic needed correction. Now the logic for the empty cases are right, but you need to move them back into the while loop again. Consider: if one of the list is empty the we need to add ALL OF THE OTHER list into the merged one. And the compare case is wrong - you need to add the smaller elements from the lists one at a time.

Collectives™ on Stack Overflow

Merge Sort in String using LinkedList

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related