Sorting using ring operations Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time. 

Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done in linear time using $\{\times,+,-,\bmod\}$ operations in unit cost RAM model where ring operations can be performed on arbitrarily large words in unit time?

I am thinking of using only $!=0$ comparison using modulo operations. If $x&gt;y$, then $x\bmod y\neq x$. If $x&lt;y$, then $x\bmod y=x$ holds. So using $x-y==0$ followed by $x - (x\bmod y)==0$ will tell if $x&lt;y$. I do not wish to have bit operations. I want more like $\mathsf{BSS}$ model.

Let me clarify my sorting problem further.

Say I have been given list of $n$ different integers $a_0,\dots,a_n$ with each $a_i\in(0,2^m-1)$. I can write down the list in a long integer form $$G=a_0+a_12^m+\dots+a_n2^{nm}$$

There is an unique permutation $\sigma\in S_{n+1}$ such
$$N=a_{\sigma(0)}+a_{\sigma(1)}2^m+\dots+a_{\sigma(n)}2^{nm}$$ is minimum.

How many ring operations (with $\bmod$) would it take in worst case for converting integer $G$ to $N$?
This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible.

I think you're going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory indexing? Comparisons? If you allow bitwise binary operations (including shifts) and either hashing or unbounded memory then it's all over, even without multiplication or division:

def sort(intlist):
    backtrans = {}
    bits = 0
    for x in intlist:
        y = 1&lt;&lt;x
        if y in backtrans:
            backtrans[y][1] += 1
        else:
            backtrans[y] = [x,1]
        bits |= y
    while bits:
        y = bits &amp;~ (bits - 1)
        x,reps = backtrans[y]
        for i in range(reps):
            yield x
        bits &amp;=~ y


There's also a linear time sorting algorithm (for large enough machine words) by Albers and Hagerup 1997 but I'm not sure which operations it needs or whether it could be adapted to use only arithmetic and not bit manipulation. The reference is:

Albers, Susanne; Hagerup, Torben (1997), "Improved parallel integer sorting without concurrent writing", Information and Computation 136 (1): 25–51.