Принты. Или наблюдения.
1. Цикл где идет merge двух векторов - тривиален. Слабым местом может быть функция резерва памяти, которая по разному реализована в win/Linux. Я не утверждаю что в linux она плохая. Возможно просто звёзды сошлись так что page или другие свойства ос по отношению к аллокаций стали неблагоприятны.
2. Что там с разрядностью 32/64? Надо проверить. Что с железом? Не пытается ли автор нас обхитрить, запуская все это на разном железе. Даже ничтожные различия в размере кешей L1 могли тут сработать.
3. Версии STL. Автор использует не сырые указатели а итераторы. Причем хитрые. Какая там логика на инкремент и на разыменование под капотом.
Чтоб отбросить мои предположения полностью - предлагаю этот цикл (предположительно самый горячий код со слов автора) переписать на указатели без STL.
4. Опции GCC надо посмотреть. Оптимизацию подвигать. O1, O2.