The way Google does this is somewhat complicated. Android apps are basically ZIP archives that make use of a few special standards. The archives themselves are compressed to be smaller using a technology called Deflate, which certainly makes the app smaller, but also makes it hard for the changes in updates to be identified.
Google, however, is now taking a different approach, which it calls file-by-file patching. This approach basically makes it easier to find changes in an app and implement those changes in a new Android APK. Check out the data savings Google has been able to achieve:
File-by-file patching basically works by comparing new and old archives. Google goes through these to identify the changes, applies the changes, then checks to ensure that the patched app matches the updated version on the Google Play Store.
There is a downside to this method — it takes longer for your phone to process. In fact, by cutting the patch size in half, it will probably double the amount of time it takes to install the update and it is a lot harder for older devices to handle the updates.
Because of the fact that it takes longer, Google is not implementing the change for all apps just yet — for now, only auto-updates that take place in the background will use the new update method.
