Code-examples/DS_Questions/Sorting at master · code-with-amitk/Code-examples · GitHub

Name		Name	Last commit message	Last commit date
parent directory ..
Hybrid_Sorting_Algo		Hybrid_Sorting_Algo
images		images
Bubble-sort.c		Bubble-sort.c
Cyclic_Sort.adoc		Cyclic_Sort.adoc
Heap_Sort.md		Heap_Sort.md
Insertion_sort.md		Insertion_sort.md
Merge Sort (Divide & Conquer).md		Merge Sort (Divide & Conquer).md
Quick_Sort.adoc		Quick_Sort.adoc
README.adoc		README.adoc

README.adoc

Table of Contents

Complexities
Stable/Unstable

Complexities

Time Complexity	Space Compelxity	Algorithms
O(n²)	O(1)	Bubble, Selection, Insertion Sort
O(nlogn)	Merge:O(n), Other: O(1)	Merge, Heap, Quick(Best) Sort
O(n)	Bucket:O(n)	Counting, Radix, Bucket Sort

O(1): space complexity constant ie No extra space needed
Worst-Case-Quick-Sort: We can use randomized version of quick sort which produces O(nlogn) in almost all cases with very high probability.

Stable/Unstable

Stability of algorithm is judged mainly on this form of input <key, value> (Eg: people names as keys and their details as values), and we wish to sort these objects by keys.
Algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted
- Stable: Bubble, insertion, merge, count
- Unstable: quick, heap