Fastest algorithm for finding two array elements that sum to x [duplicate]

Announcement of the exercise: https://cses.fi/problemset/task/1640/

I would like to understand why one algorithm is much faster than another (about 25 times) when I think they have the same complexity O(n log n) but the fastest one should in principle loop 1 more time on my list so I would have really thought it slower.

Slow:

#include <bits/stdc++.h> using namespace std; int main() { int n, x; cin >> n >> x; vector<int> a(n); map<int, int> vals; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { if(vals.count(x - a[i])){ cout << i + 1 << " " << vals[x - a[i]] << "\n"; return 0; } vals[a[i]] = i + 1; } cout << "IMPOSSIBLE" << '\n'; } 

fast:

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, x; cin >> n >> x; pair<int, int> arr[n]; for (int i = 0; i < n; i++) { cin >>arr[i].first; arr[i].second = i + 1; } sort(arr, arr + n); int i = 0, j = n - 1; while (i < j) { int sum = arr[i].first + arr[j].first; if (sum == x) { cout << arr[i].second << ' ' << arr[j].second; return 0; } else if (sum < x) { i++; } else { j--; } } cout << "IMPOSSIBLE"; return 0; }