How to understand Sort in Algo?

[romanjoy]

Bubble Sort

• Swapping elements (array's length -1) times
• T(n) = O(n^2), in-place & stable sort

[romanjoy]

Insertion Sort

• From second element, compare with left-side unsort elements
• Un-sort list equals with sorted list in loop
• T(n) = O(n^2), in-place sort & stable sort

[romanjoy]

Selection Sort

• As first or last element is min value and store index
• Find out min value & min index in the rest of list
• T(n) = O(n^2), in-place sort, unstable sort, best-case: O(n^2), worst-case: O(n^2)

[romanjoy]

Divide-and-Conquer Approach

Divide

This involves dividing the problem into smaller sub-problems.

Conquer

Solve sub-problems by calling recursively until solved.

Combine

Combine the sub-problems to get the final solution of the whole problem.

https://www.baeldung.com/cs/divide-and-conquer-strategy

Merge Sort

Process

• T(n) = O(nlogn), stable sort
• Out-place, need another array memory to copy the merge sorted list