1

I'm kind of new to this but trying to learn as quickly as possible. I am trying to implement a merge sort using stacks. I have no errors as such in my code but i get an array out of bounds error when i run the code. Any help would be greatly appreciated.

As i envision it, the merge sort function splits the stack in 2 (Left and Right) and then calls the merge function which sorts and merges them.

public static void main(String[] args) { Stack<Integer> myStack = new Stack<>(); Random r = new Random(); int size= 30; for (int i = 0; i < size;i++) { myStack.add(r.nextInt(200)); System.out.println(myStack.peek()); } MergeSort(myStack); System.out.println("-------"); for (int i = 0; i < size; i++) { System.out.println(myStack.pop()); } } private static Stack<Integer> MergeSort(Stack<Integer> input) { Stack<Integer> Result; Stack<Integer> Left = new Stack<>(); Stack<Integer> Right = new Stack<>(); if (input.size() <= 1) { return input; } int midpoint = input.size() / 2; for (int i = 0; i < midpoint; i++) { Left.add(input.get(i)); } for (int i = midpoint; i < input.size(); i++) { Right.add(input.get(i)); } Left = MergeSort(Left); Right = MergeSort(Right); Result = Merge(Left, Right); return Result; } private static Stack<Integer> Merge(Stack<Integer> Left, Stack<Integer> Right) { Stack<Integer> Result = new Stack<>(); while (Left.size() > 0 && Right.size()>0) { if (Left.get(0) < Right.get(0)) { Result.add(Left.get(0)); Left.removeElementAt(0); } else { Result.add(Right.get(0)); Right.removeElementAt(0); } } while (Left.size()> 0) { Result.add(Left.get(0)); Left.removeElementAt(0); } while (Right.size() > 0) { Result.add(Right.get(0)); Right.removeElementAt(0); } return Result; }

This is the console output.

run: 10 73 82 74 4 40 86 119 102 83 122 5 164 50 25 117 57 153 95 155 70 115 61 162 55 190 35 171 150

44

44 150 171 35 190 55 162 61 115 70 155 95 153 57 117 25 50 164 5 122 83 102 119 86 40 4 74 82 73 10 BUILD SUCCESSFUL (total time: 0 seconds)

Improve this question
5
  • 2
    In your main method you don't receive the result of call to MergeSort(myStack); Commented Oct 22, 2013 at 11:18
  • Can you post the exception's stacktrace, please? Commented Oct 22, 2013 at 11:24
  • 1
    As an aside, to follow standard java conventions variables and method names should begin with lowercase letters. Commented Oct 22, 2013 at 11:31
  • Thank you for the comments. I am working from an example made by a colleague who is not here to help so i decided just to copy names exactly. I shall use lower case in the future. Not quite sure how to solve the problem with my main method, hence the post. Commented Oct 22, 2013 at 11:54
  • @NickB here you have a visual explanation stackoverflow.com/a/23695092/3315914 Commented May 19, 2014 at 17:22

1 Answer 1

Reset to default
2

In your function Merge: if (Left.get(0) < Right.get(0)) you wrote Result.get(Left.get(0)) instead of Result.add(Left.get(0))

Another thing: in your main function when printing the sorted stack: Do you really want to use .peek() (it only looks at the top of the stack)?

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

2 Comments

Thank you! Such a silly mistake. What should i use instead of .peek()? I tried pop but that doesn't seem to work. I now get the original stack printed in reverse. I have updated my code with the correction.
First thing: myStack = MergeSort(myStack) // get result of MergeSort (overrides the original stack). Second: use pop and in your Merge function you change the condition in your if-clause: Left.get(0) > Right.get(0). But remember: after popping all the element your stack will be empty.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.