N can be as big as 10^9. A vector will need to allocate memory for this many elements, and that’s got to take some time.
The map on the other hand, will only allocate memory for the elements it needs - n/2, n/3 and n/4 (recursive of course) but that’s got to be a lot less.