When Galaxies Collide! It sounds like an early science fiction novel. However, analysis of Hubble measurements shows that our own Milky Way galaxy is moving toward a head-on collision with our nearest neighbor, the Andromeda galaxy (also known as M31). The collision will start in about four billion years, and over the following three billion years the two spiral galaxies will coalesce into a large elliptical galaxy. Based on this data, NASA has produced a video of the upcoming collision.
The story begins and ends with Hubble. The beginning is Edwin Hubble, who established in 1924 that some nebulae in the skies were far enough away that they could not be part of the Milky Way galaxy. Hubble accomplished this by using the new 100-inch Mount Wilson telescope to discover Cepheid variable stars in M31. Cepheid variables have a fixed relationship between brightness and their period of variability. As such, their apparent brightness allows their distance to be easily estimated.

Hubble also demonstrated that the redshift of galaxies (first discovered in 1912 by Vesto Silpher) was proportional to their distance from our galaxy. Redshift of the spectral lines in the light from a galaxy reflects its velocity relative to our galaxy. The cosmological redshift is caused by the expansion of the Universe. Some nearby galaxies, however, such as M31, show a blue shift rather than a red shift, showing that they have a physical motion toward us that is larger then the cosmological redshift.
Some 90 years later, we know that M31 is about 2.5 million light-years away, and is approaching our galaxy at about 109 km/sec. However, until now we have not been able to measure the perpendicular speed of M31, so could not tell if M31 would collide with us, brush by, or miss.
The end of the story also owes much to a different Hubble - the Hubble Space Telescope. The only accurate approach to measure the tangential speed of M31 is to observe proper motion of M31's stars against a background of distant galaxies. This is a difficult problem, as to make an accurate go-nogo collision prediction we must measure proper motions with a resolution of 20-30 microarcseconds. For comparison, Earth's Moon has an angular diameter of about two billion microarcseconds, and the required resolution is that required to resolve objects separated by two inches on the Moon's surface.

Only the Hubble is capable of such precise measurement, and then only of objects which appear in the same deep view image. Such an image is about a thousand light-years wide at the distance of M31, which does not allow measurement of sufficiently small transverse motions. It is therefore necessary to perform sophisticated averaging procedures over images of stars bright enough that their image is spread over a number of pixels on the Hubble CCD detectors. When this was carried out, the measured transverse motion was statistically equal to zero - meaning a head-on collision with M31 is in our remote future.

Computer simulations derived from Hubble's data show that it will take an additional two billion years after the encounter for the interacting galaxies to completely merge under the tug of gravity and reshape into a single elliptical galaxy similar to the kind commonly seen in the local universe. The dynamics of the collision are shown in the following video, which traces the evolution of the Milky Way and Andromeda galaxies over the next 8.2 billion years at a rate of 105 million years per second.
Attracted by their mutual gravity, the two galaxies encounter each other in a head-on collision about four billion years from now. The thin disk shapes of these spiral galaxies are strongly distorted and irrevocably transformed by the encounter. After an additional two billion years, the two galaxies will merge to form a single elliptical galaxy.
The mosaic image below shows what the predicted galactic collision will look like in Earth's night sky over the next seven billion years.

Although the galaxies will plow into each other, stars inside each galaxy are so far apart that they will not collide with other stars during the encounter. However, the stars will be thrown into different orbits around the new galactic center. Simulations show that our solar system will probably be tossed much farther from the galactic core than it is today.

What could be worse for the Earth than a galactic collision? Well ... just about anything, it seems. The closest average approach of stars in the spiral arms during such a collision will be about a tenth of a light year. Such distant encounters produce very little terror for individual worlds.
In addition, the Earth faces much more significant problems over this time scale. The Sun is approaching its transition to a red giant star. This will cause the oceans to evaporate in about one billion years. All water will be lost from the planet after three billion years, so any remnants of our present biosphere will be destroyed by that time, if not sooner. And two billion years later the Sun will expand into a red giant large enough to engulf the Earth. In view of such a interesting future history, a galactic collision seems a very small concern indeed.