It's worth pointing out the guidelines the USA itself applies to U.S. passport holders:
7 FAM 1330 APPENDIX D BIRTH OUTSIDE THE UNITED STATES - CURRENT SOVEREIGNTY RULE
a. It is the Department of State policy that place of birth in a U.S. passport should reflect the current sovereignty as determined by the Office of the Geographer (INR/GGI) and the regional geographic bureau.
b. As a general rule, the country that currently has sovereignty over the actual place of birth is listed as the place of birth, regardless of when the birth occurred. Passport authorizing officers must use the country of birth as it is now known for a place of birth listing, unless otherwise specified in this appendix.
c. For a location whose sovereignty is in dispute, is not yet resolved, or is not recognized by the United States, this appendix provides specific guidance.
Source: 7 FAM 1300 APPENDIX D
I'm not sure whether France has a similar guideline, but if they don't, going with the above (meaning: Algeria, not France) may be your safest bet. This would also be in line with Spehro's answer.