Merge Sort String Java

Question

I am writing a program to merge sort words in a string. But when I run my cod it seems to be loosing some data in some places. I tested it with the string: "hello world the cat sat on the bloody mat" but all i get back is [bloody, cat, hello, mat]

Here is my code:

package mergeSort;

import java.util.LinkedList;

public class mergeSort
{
    public static String sort(String userInput)
    {
        if (userInput == null)
        {
            return "";
        }
        LinkedList<String> input = toList(userInput);

        String output = MergeSort(input).toString();

        return output;
    }

    private static LinkedList<String> toList(String input)
    {
        LinkedList<String> output = new LinkedList<String>();
        String[] array = input.split("\\s");

        for (String element : array)
        {
            output.addFirst(element);
        }
        return (output);
    }

    private static LinkedList<String> MergeSort(LinkedList<String> inputstring)
    {
        LinkedList<String> sequence1 = new LinkedList<String>();
        LinkedList<String> sequence2 = new LinkedList<String>();

        if (inputstring.size() <= 1)
        {
            return inputstring;
        }

        for (int index = 0; index <= (inputstring.size() / 2); index++)
        {
            sequence1.addLast(inputstring.removeFirst());
        }
        while (!(inputstring.isEmpty()))
        {
            sequence2.addLast(inputstring.removeFirst());
        }

        sequence1 = MergeSort(sequence1);
        sequence2 = MergeSort(sequence2);

        return merge(sequence1, sequence2);
    }

    private static LinkedList<String> merge(LinkedList<String> sequence1,
            LinkedList<String> sequence2)
    {
        LinkedList<String> merged = new LinkedList<String>();

        while (!(sequence1.isEmpty()) && !(sequence2.isEmpty()))
        {
            if (sequence1.peekFirst().compareTo(sequence2.peekFirst()) < 0)
            {
                merged.addLast(sequence1.removeFirst());
            }
            else
            {
                merged.addLast(sequence2.removeFirst());
            }
        }

        while (!(sequence1.isEmpty()))
        {
            merged.addLast(sequence1.removeFirst());
        }
        while (!(sequence1.isEmpty()))
        {
            merged.addLast(sequence2.removeFirst());
        }

        return (merged);
    }
}

The testerclass:

package mergeSort;

public class mainTester
{

    public static void main(String[] args)
    {
        String test = "hello world the cat sat on the bloody mat";

        System.out.println(mergeSort.sort(test));

        System.exit(0);

    }

}

Answer 1

The problem is here:

    while (!(sequence1.isEmpty()))
    {
        merged.addLast(sequence1.removeFirst());
    }
    while (!(sequence1.isEmpty()))
    {
        merged.addLast(sequence2.removeFirst());
    }

In your merge function. Both loops check sequence1 for emptiness. Replace the second sequence1 with sequence2 in the loop condition and all will be well.