#C - 2547172 for 55986 inputs

##Algorithm:

##Analysis:

C - 2547172 for 55986 inputs

Algorithm:

Analysis:

#include <assert.h>
#include <stdio.h>
#define SIZE 6
int s0[SIZE + 1];
int s1[SIZE + 1];
int s2[SIZE + 1];
int
count(int *stack)
{
 return stack[0];
}
int
top(int *stack)
{
 return stack[stack[0]];
}
void
push(int *stack, int value)
{
 assert(count(stack) < SIZE && "stack overflow");
 assert((stack == s0 || count(stack) == 0 || value <= top(stack)) && "stack order violated");
 stack[++stack[0]] = value;
}
int
pop(int *stack)
{
 int result = stack[stack[0]];
 assert(count(stack) > 0 && "stack underflow");
 stack[stack[0]] = 0;
 stack[0]--;
 return result;
}
int permutations;
void
permute(int len, int range, void (*cb)(void))
{
 int i;
 if(len == 0)
 {
 permutations++;
 cb();
 return;
 }
 for(i = 1; i <= range; i++)
 {
 push(s0, i);
 permute(len - 1, range, cb);
 pop(s0);
 }
}
void
print(void)
{
 int i;
 for(i = 1; i <= count(s0); i++)
 {
 printf("%d ", s0[i]);
 }
 printf("\n");
}
int save[SIZE + 1];
void
copy(int *src, int *dst)
{
 int i;
 for(i = 0; i <= SIZE; i++)
 {
 dst[i] = src[i];
 }
}
int total;
void
move(int *src, int *dst)
{
 total++;
 push(dst, pop(src));
}
void
merge(void)
{
 while(1)
 {
 if(count(s1) == 0 && count(s2) == 0)
 {
 break;
 }
 else if(count(s1) == 0 || (count(s2) > 0 && top(s2) < top(s1)))
 {
 move(s2, s0);
 }
 else
 {
 move(s1, s0);
 }
 }
}
void
reverse(void)
{
 while(1)
 {
 while(count(s2) == 0 || top(s0) == top(s2))
 {
 move(s0, s2);
 }
 if(count(s0) == 0 || top(s2) < top(s0))
 {
 while(count(s2) > 0)
 {
 move(s2, s0);
 }
 break;
 }
 while(count(s0) > 0 && (count(s1) == 0 || top(s0) <= top(s1)))
 {
 move(s0, s1);
 }
 while(count(s2) > 0)
 {
 move(s2, s0);
 }
 merge();
 }
}
void
sort(void)
{
 while(1)
 {
 if(count(s0) == 0)
 {
 merge();
 reverse();
 break;
 }
 else if(count(s1) == 0 || top(s1) >= top(s0))
 {
 move(s0, s1);
 }
 else if(count(s2) == 0 || top(s2) >= top(s0))
 {
 move(s0, s2);
 }
 else
 {
 merge();
 }
 }
}
void
helper(void)
{
 copy(s0, save);
 sort();
 copy(save, s0);
}
int
main(void)
{
 permute(1, 6, helper);
 permute(2, 6, helper);
 permute(3, 6, helper);
 permute(4, 6, helper);
 permute(5, 6, helper);
 permute(6, 6, helper);
 printf("%d\n", permutations);
 printf("%d\n", total);
 return 0;
}

#include <assert.h>
#include <stdio.h>
#define SIZE 6
int s0[SIZE + 1];
int s1[SIZE + 1];
int s2[SIZE + 1];
int
count(int *stack)
{
 return stack[0];
}
int
top(int *stack)
{
 return stack[stack[0]];
}
void
push(int *stack, int value)
{
 assert(count(stack) < SIZE && "stack overflow");
 assert((stack == s0 || count(stack) == 0 || value <= top(stack)) && "stack order violated");
 stack[++stack[0]] = value;
}
int
pop(int *stack)
{
 int result = stack[stack[0]];
 assert(count(stack) > 0 && "stack underflow");
 stack[stack[0]] = 0;
 stack[0]--;
 return result;
}
int permutations;
void
permute(int len, int range, void (*cb)(void))
{
 int i;
 if(len == 0)
 {
 permutations++;
 cb();
 return;
 }
 for(i = 1; i <= range; i++)
 {
 push(s0, i);
 permute(len - 1, range, cb);
 pop(s0);
 }
}
void
print(void)
{
 int i;
 for(i = 1; i <= count(s0); i++)
 {
 printf("%d ", s0[i]);
 }
 printf("\n");
}
int save[SIZE + 1];
void
copy(int *src, int *dst)
{
 int i;
 for(i = 0; i <= SIZE; i++)
 {
 dst[i] = src[i];
 }
}
int total;
void
move(int *src, int *dst)
{
 total++;
 push(dst, pop(src));
}
void
merge(void)
{
 while(1)
 {
 if(count(s1) == 0 && count(s2) == 0)
 {
 break;
 }
 else if(count(s1) == 0 || (count(s2) > 0 && top(s2) < top(s1)))
 {
 move(s2, s0);
 }
 else
 {
 move(s1, s0);
 }
 }
}
void
reverse(void)
{
 while(1)
 {
 while(count(s2) == 0 || top(s0) == top(s2))
 {
 move(s0, s2);
 }
 if(count(s0) == 0 || top(s2) < top(s0))
 {
 while(count(s2) > 0)
 {
 move(s2, s0);
 }
 break;
 }
 while(count(s0) > 0 && (count(s1) == 0 || top(s0) <= top(s1)))
 {
 move(s0, s1);
 }
 while(count(s2) > 0)
 {
 move(s2, s0);
 }
 merge();
 }
}
void
sort(void)
{
 while(1)
 {
 if(count(s0) == 0)
 {
 merge();
 reverse();
 break;
 }
 else if(count(s1) == 0 || top(s1) >= top(s0))
 {
 move(s0, s1);
 }
 else if(count(s2) == 0 || top(s2) >= top(s0))
 {
 move(s0, s2);
 }
 else
 {
 merge();
 }
 }
}
void
helper(void)
{
 copy(s0, save);
 sort();
 copy(save, s0);
}
int
main(void)
{
 permute(1, 6, helper);
 permute(2, 6, helper);
 permute(3, 6, helper);
 permute(4, 6, helper);
 permute(5, 6, helper);
 permute(6, 6, helper);
 printf("%d\n", permutations);
 printf("%d\n", total);
 return 0;
}

There is a lot of room for improvement here. For my own sanity, I simplified this so that it was only possible to inspect the top element of each stack. Lifting this self-imposed restriction would allow optimizations like determining the final order in advance and trying to minimize the number of moves required to achieve it.

There is a lot of room for improvement here. For my own sanity, I simplified this so that it was only possible to inspect the top element of each stack. Lifting this self-imposed restriction would allow optimizations like determining the final order in advance and trying to minimize the number of moves required to achieve it. A compelling example is that my implementation has worst case behavior if the main stack is already sorted.

##Analysis:

• Additional space complexity is O(n) (for the two auxiliary stacks), which is good, since that was a requirement of the problem.
• Time complexity is O(n^2) by my count. Corrections are welcome.