tại sao hàm sort c++ lại có độ phức tạp là o(nlogn), cho vd

$#doanthevu$

( Hàm sort trong C++ thường được khai triển bằng quicksort  hoặc mergesort )

Để giải thích vì sao hàm sort trong C++ lại có độ phức tạp là O(n log n), chúng ta sẽ xem một ví dụ cụ thể :

+ Ta có 1 mảng gồm 8 phần tử được sắp xếp lộn xộn, yêu cầu là sắp xếp các phần tử theo thứ tự tăng dần: 

[5, 2, 4, 6, 1, 3, 7, 8]

-> Quá trình sắp xếp sẽ diễn ra như sau:

+ Chia mảng thành 2 nửa, mỗi mảng gồm 4 phần tử 

[5, 2, 4, 6]
[1, 3, 7, 8]

+ Chia 2  mảng này thành  4  mảng con:

[5, 2], [4, 6]
[1, 3], [7, 8]

+ Sắp xếp 4 mảng con này:

[2, 5], [4, 6]
[1, 3], [7, 8]

+ Gộp 4  mảng con này thành 2 mảng:

[2, 5, 4, 6]
[1, 3, 7, 8]

+ Gộp 2  mảng này thành mảng đã sắp xếp:

[1, 2, 3, 4, 5, 6, 7, 8]

( Mỗi lần chia nhỏ mảng, số lượng chia nhỏ sẽ diễn ra log n  lần -> tổng số phép so sánh là khoảng n * log n )