"The energy involved in Mars orbit, would be it's mass halved times it's velocity squared.
Mars mass is 10^24 kg
And it's orbital velocity is 24,100 m/s."

A space rock which was 1 km in diameter and having a density of less than 2, would weigh about 1 billion tonnes [or 10^12 kgs].

There are about 1000 near earth objects [NEOs] which are about 1 km in diameter or larger.
One could assume that they might be "something equal" to about 1000 space rocks of about 1 km in diameter which might be suitable to impact Mars in order to change it's orbit. With suitable being defined as objects requiring less than 1 km per second of delta-v to alter it's orbit. And requiring a time period of less than 50 years. And assuming the result of such a impact is to transfer about 5 km/sec or more of the impactor mass towards altering Mars' orbit- so that one is using 1 km/sec or less of delta-v in order to achieve 5 km/sec or more of delta-v to Mars orbit.

So the ballpark is 1 trillion tonnes in total [10^15 kgs] and about average of 5 km/sec [5000 meters per second].
In terms of kinetic energy:
Kinetic energy = 1/2 mass times velocity squared.
So, for joules it's 5000^2 times 5 times 10^14
Which is 1.25 times 10^22 joules.

In comparison Mars orbital energy expressed in joules is
24,100^2 times 5 times 10^23
Which is 2.9 times 10^32 joules

Or about 20 billion times more orbital energy than our 1000 1km space rock imparting 5 km/sec.

Our Moon is about 1/80th of the mass of Earth.
If our moon was in an orbit at the same distance as Earth BUT was traveling in the opposite direction. And it directly impacted the Earth, this would significantly alter the Earth's Orbit [and obviously killing everyone {and microbe} on Earth].

If did the same thing but our Moon size object hit Mars, Mars orbit could be so altered that it's perihelion could be somewhere around Mercury's orbit.
Some planetary masses:
Earth: 5.9736 times 10^24 kg
Mars: 0.64185 times 10^24 kg
Moon: 0.07349 times 10^24 kg
http://nssdc.gsfc.nasa.gov/planetary/factsheet/

And [generally] something going in the opposite direction in a orbit would impart the most amount of energy per mass of the object- in terms of altering it's orbit. And [generally] objects in our system are not going in the opposite direction of the orbits of the planets.
And so, even though most impactor could hit a planetary body at a higher velocity than say 20 km/sec, this doesn't mean it will give or take away 20 km/sec [or a high percentage] of the impactor mass to the planet's orbital velocity- and some that energy could change planet's rotation [random impactors [of say, the last 4 billion years] probably have a larger affect upon a planet's rotation than compared to it's orbit- I mean in terms of a possible noticeable affect].

So unless one is going to get space rocks from the Kuiper Belt or beyond and some interesting gravity assists [and decades to centuries of time], the best rock would be one which was in a highly elliptical around the sun and traveling a very low speed at it's Aphelion which near Mars distance. These might give you much more than 5 km/sec as far as changing Mars orbit, but it seems these type of rocks are somewhat rare- they would be [mostly] a certain/limited type of NEOs or earth crossing asteroids.
And in addition these types of asteroids could have more value for other purposes other crashing them into Mars.