Heapsort
হিপসর্ট
Array থেকে max-heap বানিয়ে root (সবচেয়ে বড়) বারবার শেষে swap করে heap ছোট করে যাওয়া sort — worst-case O(n log n), in-place, তবে unstable।
also: heap sort
দুই phase:
- Build-heap — bottom-up sift-down, O(n)
- Extract — root-কে শেষ index-এর সাথে swap, heap size কমাও, sift-down; n−1 বার, প্রতিবার O(log n)
Best থেকে worst — সব case-এ O(n log n), extra memory O(1)।
তবু quicksort প্রায়ই জেতে: heap-এ parent↔child access দূরে-দূরে jump করে — cache-unfriendly। মূল্যবান জায়গা: introsort quicksort-এর O(n²) দুর্ভাগ্যে heapsort-এ fallback করে; hard real-time system-এও নিরাপদ বেছ।