After graduated from college, I rarely study in algorithm questions, because I don't have to implement special algorithm most of my time. I did use BFS one or twice when I deal with the workflow problem, but most of the time you don't bother. Also, software engineering is a board topic. Being a good software engineer means more than just using efficient algorithm, and a readable O(n^2) solution is better than a complicated O(nlogn) solution if there are no performance issues.
Therefore, this is very refreshing and eye-opening when I revisit the merge sort algorithm.
The implementation of merge sort is O(nlogn) because T(n) = 2T(n/2) + C, the C is n, you could think of we do this O(n) operation log(n) times.
This is something that I oversee when I learn this algorithm, when C is something that is better then O(n^2) this is automatically a better solution than O(n^2).
Let say we want to count the number of value which is smaller than self like this question.
Since counting numbers that is larger than self is O(n), then we can use the idea of merge sort to divide and conquer the problem and obtain O(nlogn).
Top comments (0)