Hitting the very first paragraph of the OP:
The north side of Borneo was among the possessions of the Sultan of Brunei, who used to be a fairly powerful potentate with a great deal of land in the Malay Archipelago. The southern shore was occupied by native tribes, and not of great interest to the various Malay kingdoms in Java, Bali, etc. Britain established a trading post at an offshore island named Labuan, by treaty with the Sultan. From this, they gradually asserted a protectorate over the Sabah area, in northeast Borneo. Meanwhile, Sir James Brooke, a british adventurer, obtained a grant of land in the western part of the north coast from the Sultan of Brunei, and established a quasi-independent kingdom, Sarawak, as the first of the White Rajahs, expanding his territory at the expense of Brunei until that state was reduced to the present small area. Sarawak was always closely linked to the U.K. and depended on the Royal Navy for protection. Viner Brooke, the 3rd rajah, was caught in Australia when the Japanese attack seized Sarawak, and after the war ceded Sarawak to the U.K. in exchange for a pension. Meanwhile Britain had extended its influence over the south end of the Malay Peninsula, establishing protectorates over each of the minor sultanates there, as well as over the reduced Brunei.
The nine protectorates became independent as Malaya in 1958, with a Paramount Sultan elected by the nine sultans from among their number. When Sarawak and Sabah were ready for independence four years later, it was decided to merge them, along with Singapore, into a new Federation of Malaysia. Singapore, as already noted, seceded from that union two years after that.
As the Dutch extended their authority over the islands of the Malay Archipelago, they took the hitherto-neglected southern part of Borneo, Kalimantan, and incorporated it into the Dutch East Indies, which gained independence as Indonesia in 1949.
Along with Borneo, there is another Indonesian island divided between two countries: Timor, half of which is Indonesian and half was formerly Portuguese Timor, and is now the independent nation of Timor Timur. (The odd name results from timo/ur being the term in various Malay dialects for “east” – the island of Timor got its name from being at the east end of the archipelago, and the new nation was the eastern half of Timor, or Timor Timur.)
(Plus of course New Guinea, now half Indonesian and half the main part of the republic of Papua New Guinea.)