Also referred to as the Algerian Revolution, the Algerian War was a brutal multi-sided struggle nominally between the French Fourth Republic and the National Liberation Front (FLN) over the matter of independence for Algeria, lasting from 1954-1962. Beneath the surface of the main conflict, however, there were also political and military struggles involving a number of groups whose aims did not exactly match those of the French or the FLN. In addition to this, the groups changed and split during the course of the war. Most notably, the war brought about the fall of the Fourth Republic and paved the way for the return of Charles DeGaulle to power; DeGaulle in turn would take a leading role in establishing the Fifth Republic. This political failure and DeGaulle's acquiescence in Algerian independence led to a split in the French Army between Gaullists and hardliners who wished to preserve the hard-won military victory, which led to the Secret Army Organization (OAS) fighting both the FLN and regular army units in Algeria. On the other side of the conflict, the FLN had to contend not only with opposition from Algerians who were opposed to independence but with a rival independence movement, the MNA. The FLN was able to quickly extinguish the small armed groups of MNA within Algeria, and the latter fought a terrorist campaign in France against the FLN and its supporters (the so-called Cafe Wars) but faded into irrelevance after Algeria obtained independence.
The war originally started as a police action under the direction of Guy Mollet, then the Socialist Prime Minister, and his Minister of the Interior, Francois Mitterrand*, but rapidly evolved into a full-scale war. Most Algerians initially wanted a peaceful resolution, but due to influence from Arab nationalists and the global wave of anti-colonialist opinion gradually moved to support the FLN. France could never reach a consensus on whether to keep the status quo, negotiate an intermediate status, or grant independence, and this lack of consensus crippled the war effort. Nevertheless, the French Army, ruthlessly applying the harsh lessons learned in Indochina, harried the FLN, spearheading their military operations with the elite paratrooper and Foreign Legion** units and supplementing the regular army units with "harkis", units of loyal Algerians, who actually outnumbered the FLN by the end of the war's military phase in 1958.
The French Communists and other leftist parties had long supported the FLN, and they comprised a large enough bloc in Parliament to prevent a consensus on what should be done with Algeria. By May 1958, the military and the political right had had enough of the obstruction; there was a fear that left to their own devices, the politicians would sell out the Army, the Harkis, and the pieds-noirs. Governor-General Soustelle returned to France to rally support for De Gaulle, and an Army junta under General Massu seized power in Algeria. Paratroopers landed on Corsica, and Massu made it clear that if Parliament didn't recall DeGaulle, the Army would march on Paris. Parliament, realizing it had lost control of the Army, voted to recall DeGaulle.
De Gaulle visited Algeria and charmed the hard-liners with his cry of Vive l'Algerie Francaise!, and his drafting of the constitution of the Fifth Republic, which included an "associated" Algeria. This initiative threatened the political survival of the FLN, which responded by setting up a provisional government that was quickly recognized by the Soviet Union, PRC, and some other Arab nations. The FLN also stepped up its campaigns of terror in Algeria and France. Despite the terror, 80% of the Muslim electorate registered to vote, and 96% of them supported the constitution. De Gaulle was elected president of the Fifth Republic in February 1959 and called on the FLN leaders to negotiate a peace, an offer which was obdurately refused. By September 1959, a combination of domestic political opposition to the war and diplomatic pressures made De Gaulle's position untenable; he began to talk about "self-determination" for Algeria.
This was regarded as a betrayal by the pieds-noirs and loyal Algerians, and the "Week of Barricades", in which colonial volunteer units rebelled and blocked the streets of Algiers. The Army did not officially support the colonials, but they took no steps to suppress them or remove the barricades, either. De Gaulle took to the television and called on the Army to remain loyal, and the state of siege in Algiers ended on February 1, 1960. The failure of the Army to support the rebels led directly to the founding of the Secret Army Organization (OAS), which struck against civilian and military supporters of the De Gaulle's policies. None of it mattered; in the end, a majority of Algerians and Frenchmen voted for independence. The pieds-noirs and harkis who did not emigrate to France were butchered by the FLN despite guarantees of their safety; almost two million of them fled to France, which was neither willing nor able to accommodate them. And so, the Algerian War ended every bit as squalidly as the Indochina War, with the politicians giving away what the military had won.
*It should be noted that Algeria was technically part of France itself and elected deputies to the French Parliament.
** Algeria had special significance to the Foreign Legion; it was their home base and historically the Legion had been forged in the initial fighting for the colony.