You have an entity A that you want to turn towards another entity B. One way to determine the direction to turn is to compute the cross-product of the direction vector of A with the vector from AB. If the value of z is positive, then you turn right. If the value of z is negative, you turn left. Is this the only way of determining which way to turn?
If you're storing your rotations as quaternions (which you probably should), you could use a quaternion lerp function to lerp from your initial rotation to the rotation you want to be at (i.e the rotation given by the vector AB with whatever your up vector is).
It sounds like this is essentially a 2D problem; if it's truly a 3D problem (one spaceship face another spaceship in free space) then you should definitely use quaternions. Traditional vectors will have odd turn patterns. But according to your question, you're just turning left or right. If you can simplify the problem down to two (x,y) positions and the angle that entity A is facing, then you can use simple 2D math:
tan((yB-yA)/(xB-xA)) is the desired angle (of A facing B). Turn towards that.
You need to account for crossing 0 degrees; for example, if the target angle is 359 degrees and you're currently looking at a 1 degree angle, you want to just turn 2 degrees clockwise rather than turning 358 degrees counterclockwise.