SortedStack implementation in Java

First up, let's both simplify your low level Stack class, and correct the Generics at the same time.

Stack

The issues with the generics are "obvious" by the numerous times you cast values that should be generically correct anyway.

You also have overly complicated logic in your push method:

public void push(T item){
    Node p = new Node((Comparable) item);
    if(head == null){
        head = p;
        return;
    }
    p.next = head;
    head = p;

}

That can be simply (note, this requires a change to Node that I describe in a moment):

public void push(T item){
    head = new Node(item, head);
}

Right, the change to Node is to add the next to the constructor:

private class Node{
    private final T data;
    private final Node next;

    public Node(T data, Node next){
        this.data = data;
        this.next = next;
    }
}

The System.exit(-1) error handling is also really horrible.... use exceptions!

Finally, why do you have a getHead() method on the Stack? It returns a value that is a private-context Node, so nobody can actually call that method.... right? I am half-surprised that Java lets that compile.

The "final" Stack class could look like:

public class Stack<T>{

    private class Node{
        private final T data;
        private final Node next;

        public Node(T data, Node next){
            this.data = data;
            this.next = next;
        }
    }

    private Node head;

    public void push(T item){
        head = new Node(item, head);
    }

    public T pop(){
        if(head == null){
            throw new IllegalStateException("Cannot pop an empty Stack");
        }

        T item = head.data;
        head = head.next;
        return item;

    }

    public T peek(){
        if(head == null){
            throw new IllegalStateException("Cannot peek an empty Stack");
        }
        return head.data;
    }

    public boolean isEmpty(){
        return head == null;
    }
}

SortedStack

This class has some simpler problems - naming, and style. It also has some algorithmic problems that may be improved.

s1 and s2 are horrible, horrible names. stack and temp would be better. But, really, there's no reason to have temp at all, you can create it for the duration of the push method only - it does not need to hang around when empty.

You also have the following, very baffling method. This is a "WTF" thing:

public int compareTo(T other){
    return compareTo(other);
}

Please explain that to me? ;-)

Throw it away!

While we are throwing things away, throw out the size as well, it's a distraction, and unnecessary.

Talking about throwing things out..... did you throw out the peek() method when it should actually be there?

One small comment on this code segment:

if((s1.peek().compareTo(item) > 0) || (s1.peek().compareTo(item) == 0)){ 

How about ( ;-) ):

if(s1.peek().compareTo(item) >= 0) {

Now, ignoring the push(T) method, the rest of the SortedStack class could simply be:

public class SortedStack<T extends Comparable<T>> {

    private final Stack<T> stack;

    public SortedStack(){
        stack = new Stack<>();
    }

    public T peek() {
        return stack.peek();
    }

    public T pop(){
        return stack.pop();
    }

    public boolean isEmpty(){
        return stack.isEmpty();
    }

    public void push(T item) {
        //TODO - fill this in ;-)
    }

}

Now, abut that push method.... how about:

public void push(T item) {
    Stack<T> temp = new Stack<>();

    // stash away all values less than the new item 
    while (!stack.isEmpty() && stack.peek().compareTo(item) < 0) {
        temp.push(stack.pop());
    }

    // keep the item
    stack.push(item);

    // restore all the smaller items.
    while (!temp.isEmpty()) {
        stack.push(temp.peek());
    }
}

Not a Stack

A Stack is a data structure where items are removed Last-In-First-Out (LIFO). This data structure does not do that. Therefore, it is not a Stack. Calling it a SortedStack is confusing as you've removed everything about it that is like a Stack and not any other type of Collection. This has the interface behavior of a PriorityQueue, why not call it that?

In a sense this works like a PriorityQueue only in O(n) runtime against the O(log n) runtime of a PriorityQueue.

A PriorityQueue does not have a runtime. It has operations which have runtimes. Presumably what you are saying is that this implementation of a PriorityQueue has a \$O(n)\$ insertion where the standard Java implementation is \$O(\log n)\$.

    public boolean isEmpty(){
        return size == 0;
    }

Why maintain a size variable? Just say

    public boolean isEmpty(){
        return s1.isEmpty();
    }

Similarly,

    public T pop(){
        size--;
        return s1.pop();

    }

could just be

    public T pop() {
        return s1.pop();

    }

Why is s2 an object field?

You only use s2 in push and don't carry over any results from use to use. Why not make it a local variable in push? Then the garbage collector could remove it between uses. Or it can sit on the heap until needed. As a general rule, it is a best practice to define all variables at the smallest scope necessary.

I also find the names s1 and s2 unclear. Why not call s1 something like storage or data? Then you could call s2 something like tempStorage or tempData. If you still use a second variable at all.

compareTo

    public int compareTo(T other){
        return compareTo(other);
    }

What do you think this does? I would expect this to crash the program if ever run. You're just having a method call itself with the same parameters. It would keep doing this until it ran out of stack space.

Why use two Stack variables internally?

        if(s1.getHead() == null){
            s1.push(item);
            return;
        }

        while(!s1.isEmpty()){
            if(s1.peek().compareTo(item) < 0){
                s2.push(s1.pop());
            }else if((s1.peek().compareTo(item) > 0) || (s1.peek().compareTo(item) == 0)){
                s1.push(item);
                break;
            }
        }
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }

Because you are holding the data in a Stack, you are doing more work than necessary. If you put the data in a List instead, you could reduce the amount of code you write. For example, you could replace all your fields with just one:

    private final List<T> data = new LinkedList<>();

Made the field final because it never changes, just the contents.

You can get rid of the constructor now. The default will be fine.

        int i = 0;
        while (i < data.size() && data.get(i).compareTo(item) < 0) {
            i++;
        }

        data.add(i, item);

This handles the case where data is empty. Then i will be 0 and the item will get added to the beginning of the list.

It handles the case where item is greater than all the items currently in data. The value i will be equal to data.size() and item will be added at the end of data.

And of course, the while loop will determine the place in data where item belongs.

You could also replace the while loop with the following for loop:

        for ( ; i < data.size() && data.get(i).compareTo(item) < 0; i++) ;

or

        for ( ; i < data.size(); i++) {
            if (data.get(i).compareTo(item) < 0) {
                break;
            }
        }

Note that i has to be defined outside the loop so that you can use it in the add operation.

I personally find the while loop to be clearest about what it is doing. Some prefer for loops whenever iterating though. The second is more verbose and perhaps clearer. The first is more compact. All three loops do the identical thing, so it's mainly personal preference which you use. As I said, I vote for the while version.