Non-recursive merge Sort using stacks
I am currently working on an assignment where I should write mergeSort using stacks! I have a pretty good idea of ββhow stacks and merges work, however I'm not sure how to end my code with stacks. I created a basic example and here I am trying to use an in-place method where I just theoretically split my array without creating a new one by changing the markers. I'm new to this and don't know how I should proceed. I think this is what I am going to do:
Basic example -> PC = 1
if (callStack.peek().PC == 1) {
if (callStack.peek().start == callStack.peek().stop) { //length <=1
callStack.pop(); //either done, or array length was 1
merge(A, callStack.peek().start, callStack.peek().mid, callStack.peek().stop);
if (callStack.empty()){
break;
}
callStack.peek().PC++;
} else {
callStack.peek().PC++;
}
continue;
}`
any left split array -> PC = 2 any right split array -> pc == 3
int mid = (callStack.peek().stop-callStack.peek().start)/2;
if (callStack.peek().PC == 2) {
if (callStack.peek().start != callStack.peek().stop) {
current = new ProgramFrame(callStack.peek().start, callStack.peek().mid, 1);
callStack.push(current);
continue;
}
}
if (callStack.peek().PC == 3) {
if (callStack.peek().start != callStack.peek().stop) {
current = new ProgramFrame(callStack.peek().mid+1, callStack.peek().stop, 1);
callStack.push(current);
continue;
}
}
merging both -> pc == 4
if (callStack.peek (). PC == 4) {merge (A, callStack.peek (). start, callStack.peek (). mid, callStack.peek (). stop);
callStack.pop();
if (!callStack.empty()) {
if (callStack.peek().PC == 2) callStack.peek().start callStack.peek().mid; //help??
if (callStack.peek().PC == 3) callStack.peek().mid+1, callStack.peek().stop; //help??
callStack.peek().PC++;
continue;
I'm sorry it's such a long post :( I'm just not sure how to fix this and how to continue ...
** also combine and my programeFrame looks good, but if you need to see them I can post them too!
source to share
No one has answered this question yet
Check out similar questions: