Scusa, ma ti è mai capitato di ordinare qualcosa? Che so, un mazzo di carte, documenti o altro? In quel caso come procedi? Non stabilisci un criterio arbitrario per stabilire come ordinare? Ad esempio peschi una carta e dici: tutte le carte minori di questa in mano, vanno a sinistra; le maggiori di questa vanno a destra (o viceversa?)

Lo stesso principio si applica in informatica (con algoritmi più o meno efficienti), indipendentemente che siano liste, array, mappe, b-tree o quant'altro.

Per rispondere alle domande:
1) la funzione < è invocata sempre sia in fase di inserimento sia fase di ricerca.
2) vedi su
3) Un libro che parli di algoritmi e strutture dati, anche se in genere sono scritti in presudo linguaggio.