Birlashtiruv saralash. Tezkor tartiblash (quicksort). Chiziqli saralash algoritmlari. Tartiblash. Mergesort effektiv tartiblash algoritmlaridan biri bo’lib uning ishlash prinsipi «bo’lib tashla va hukmronlik qil»

Nimaga tartiblashdan avval aralashtirish kerak? 
Yuqorida e’tibor bergan bo’lsangiz, 2.1, 2.1.2, 2.1.2.1 qismlarda biz pivot bo’yicha array’ni 
ikkiga bo’la olmadik. Sababi pivot eng kichik (eng katta) element bo’lib qoldi. 
Aralashtirishdan maqsad esa tanlanadigan pivot iloji boricha eng kichik (eng katta) element 
bo’lib qolmasligining oldini olish uchundir. Demak agar array yaxshi aralashmagan bo’lsa, 
bizda ikkiga bo’lish (partition) effektiv chiqmaydi. Quicksort maksimum darajada aralashgan 
array’lar uchun samarali ishlaydi. 
Quicksort’ning uning o’rtacha time complexity’si O(1.39*n log n), Mergesortdan 39% ko’proq. 
Quicksortning ajoyibligi shundaki, u qo’shimcha array’siz, berilgan arrayning o’zida partition’ni 
amalga oshiradi va Mergesortga nisbatan kamroq almashtirishlar qiladi. 
Qo’shimcha array ishlatilsa, funksiya soddaroq (va qisqaroq) ko’rinishda bo’ladi, ammo 
bunda Quicksort’ni ishlatishdan foyda yo’qoladi. 
Worst case – O(1/2 N
2
) – allaqachon tartiblangan array uchun. Chunki bu holatda pivot 
array’ni ikki qismga bo’la olmaydi.
function
quickSort
(arr) 
{ 
function
partition
(arr, low, high) { 
let
i 
=
low, j 
=
high 
+
1
while
(
true
) { 
while
(arr[low] 
>
arr[
++
i]) { 
if
(i 
==
high) 
break
; 
} 
while
(arr[low] 
<
arr[
--
j]) { 
if
(j 
==
low) 
break
} 
if
(i 
>=
j) 
break
; 
[arr[i], arr[j]] 
=
[arr[j], arr[i]] 
} 
[arr[low], arr[j]] 
=
[arr[j], arr[low]] 

---

return
j 
} 
function
sort
(arr, low, high) { 
if
(high 
<=
low) 
return
let
j 
=