• Sorting is any process of ordering or categorizing items systematically
• It helps us find items easier and faster when the data are sorted

Insertion Sort

• วิธีทำสามารถดูได้ที่ Insertion Sort

Performance

• When data are already in order: $O(n)$
• When data are reverse in order: $O(n^2)$
• Complexity depends mainly on the number of comparisons and swapping

Selection Sort

• วิธีทำสามารถดูได้ที่ Selection Sort

Performance

• When data are already in order: $O(n^2)$
• When data are reverse in order: $O(n^2)$
• Complexity depends mainly on the number of comparisons and swapping

Merge Sort

• วิธีทำสามารถดูได้ที่ Merge Sort

Performance

• Merge sort using the array data structure requires and extra storage (temp array) of size $\frac{n}{2}$ for the divided data and merged data at each round
• The complexity depends on comparisons, assign data to the temp array, and copying data back to the original array
• Merge sort has worst case performance of $O(n\log n)$

Quick Sort

• วิธีทำสามารถดูได้ที่ Quick Sort

Limitation

• It may require an extra storage to save the groups of data +-
• Selecting a good pivot is also a challenge

Performance

• The pivot divides the array each time into one big subarray while the other array empty: $O(n^2)$
• In the best case, the pivot divides the array each time into two parts of about the same size: $O(n\log n)$

Sorting Complexity (Big-O)