Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?

As far as I know, the only way to sort with $O(\log n)$ comparison on each element is to construct an AKS sorting network for $n$ inputs, and run the input on the sorting network.

AKS is not easy to implement and has an impractical constant factor, so there are motivations to search for other algorithms.

An algorithm with $O(\log^2 n)$ comparisons per item which does not seem to imply a sorting network is presented here. (iirc, this was first presented by Rob Johnson at Stony Brook's algorithm seminar).
Upon discussing this with Michael T. Goodrich, it seems that the parallel sorting algorithm by Cole for EREW PRAM does the job. See


Richard Cole: "Parallel Merge Sort". SIAM J. Comput. 17(4): 770-785 (1988).


In that algorithm there are $O(\log n)$ rounds and in each round each element participates in $O(1)$ comparisons. (One has to understand the algorithm to see that we do not abuse of making copies of each element.)

An extension of that algorithm for parallel pointer machine is given in 


M.T. Goodrich, S.R. Kosaraju: "Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation". J. ACM 43(2): 331-361 (1996).