Create a custom stack class with a swap method?

[rcgldr]

I've written a poly phase merge sort using 3 "stacks" in C++. The key part of the logic is to merge from containers A and B into container C. It's expected for A or B to go empty with lots of data remaining on B or A. To deal with this, when A or B go empty, the empty container is swapped with C and the merge continues, until A and B go empty at the same time, in which case the sort is done. Without the swapping, then I'd have to code for all 6 possible permutations of A, B, C.

For the C++ program, since in this case the stacks have a maximum size, each stack is simply an array with a stack pointer. Push is *--stack_pointer = value, pop is value = *stack_pointer++. This is quick, when sorting 16 million pseudo random 32 bit integers in 64 bit mode (16 registers) on my system, the poly phase merge sort using 3 "stacks" (a programming challenge) takes 1.6 seconds, versus 1.5 seconds for a 2 way merge sort, 1.4 seconds for a 4 way merge sort, or 1.45 seconds for quick sort.

The programming challenge here is to emulate poly phase merge sort on 3 tape drives, where data is written forwards and read backwards, which is emulated using stacks (or anything LIFO).

One alternative would be to use a linked list for the stack, which should work in Java, since a dummy / sentinal node's next pointer could be changed to point to any list, providing a means to swap "pointers" to lists. This would be slower, but Java apparently isn't meant for performance.

 

[jedishrfu]

If C is the output of the sort why are you bringing it back into the mix?

I would think you'd have a test if one queu was empty to return a maximal key so that the other queue would be selected and its elements added to C or a specialized method to take all of the remaining queue and add it to C.

A linked list strategy would probably speed things up as once one queue is empty the remaining one is simply linked to the end of C.

 

[rcgldr]

If C is the output of the sort why are you bringing it back into the mix?

This came up at another forum, asking about implementing an efficient sort using only 3 "stacks" and some local variables, unfortunately in Java for this particular question, although the 3 stack sort question has come up before for other languages.. I don't have Java, so I coded up a few examples in C++, wrongly assuming it had something equivalent to an intelligent swap like C++ std::swap for vectors or containers in general.

Using a poly phase merge sort only needs to distribute some data from A to B and C at the start, and afterwards, it only merges data, without any copies. It's complicated by the fact that since stacks are used, the merge operations alternate between ascending and desceding, and the runs sizes in A, B, C can either increment or decrement at some point in A or B or C (only one of them will have an increment / decrement point at a time).

I would think you'd have a test if one queu was empty to return a maximal key so that the other queue would be selected and its elements added to C

A poly phase merge sort is an "unbalanced" sort. It starts off merging A and B into C, but if A goes empty, it switches to merging B and C into A. Then B should go empty next, in which case it continues merging C and A into B. Wiki article:

http://en.wikipedia.org/wiki/Polyphase_merge_sort

A linked list strategy would probably speed things up ...

For C++, I'm using an array with a stack like pointer into the array. For example an array of size N named A[]. element *Stack_Pointer is initialized to A + N (== &A[N]). As mentioned before, push(value) == *--stack_pointer = value. Pop() returns *stack_pointer++, these are fast operations but this strategy only works when the maximum size of the stack is known in advance. For variable size stack, stack could work from the start of an array, which could then be reallocated if it needed to grow. In this case push(value) = *stack_pointer++ = value. pop returns *--stack_pointer, and peek returns *(stack_pointer - 1).

 

[Mark44]

This thread is tagged as being about Java. Is that a mistake?

 

[D H]

This thread is tagged as being about Java. Is that a mistake?

I believe he's asking how to implement a swap function in Java. You can't.

You can come close:

/**
* Not really a swap function, but when used right, it acts as one.
* Usage: y = pseudo_swap_function_if_called_correctly (x, x=y);
*/
<T> pseudo_swap_function_if_called_correctly (T a, T b) {
    return a;
}

This is massively devious and prone to error. I would never call that function swap because that is not what it does. It simply returns the first argument. The second argument is dropped on the bit floor.

 

[rcgldr]

This thread is tagged as being about Java. Is that a mistake?

The tag is correct, it should be Java. Being new to Java, I didn't realize that Java arrays were handled as references, Java int a[] is similar to C / C++ int *a. Here's an example Java stack class that includes a swap function member:

class fstack{                               // fast fixed size stack
    int []ar;                               // array
    int sz;                                 // size
    int sp;                                 // stack pointer
    public dstack(int sz){                  // constructor with size
        this.ar = new int[sz];
        this.sz = sz; 
        this.sp = sz;
    }
    public void push(int d){
        this.ar[--sp] = d;
    }
    public int pop(){
        return this.ar[sp++];
    }
    public int peek(){
        return this.ar[sp];
    }
    public boolean empty(){
        return sp == sz;
    }
    public int size(){
        return sz-sp;
    }
    public void swap(dstack othr){
        int []tempar = othr.ar;
        int tempsz = othr.sz;
        int tempsp = othr.sp;
        othr.ar = this.ar;
        othr.sz = this.sz;
        othr.sp = this.sp;
        this.ar = tempar;
        this.sz = tempsz;
        this.sp = tempsp;
    }
}