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!

+3


source to share





All Articles