sorting_algo

this repository is meant to store some of the sorting algorithms

---

---

• Merge Sort

  • Complexity T(n)= 2T(n/2) + 0(n) i.e. T(n)=nlog(n)

  • Only known algorithm which is external sorting.

  • not in place since it requires 0(n) additional space

  • Complexity in best as well as in worst case is nlog(n)

  • In merge sort partition requires 0(1) time while merging requires 0(n) time

---

• Quick Sort

  • Complexity T(n)

  • It is an example of internal sorting since all the elements are needed to be sorted at once.

  • A perfect example of in place out of the given sorting algorithms.

  • Worst Case Complexity T(n)=T(n-1)+0(n)

  • Best Case Complexity T(n)=T(n/2)+0(n)

  • In quick sort most time is taken by partition part of the algorithm while merging requires 0(n) time

  • Complexity can be decreased through randomized prioritization of elements

---

• Insertion Sort

  • Best Case Complexity T(n)=0(n)

  • Worst Case Complexity T(n)=0(n^2)

  • An example of in place algorithm

  • An example of internal sorting

---

• Bubble Sort

• Complexity T(n)=O(n)
• Maximum number of swaps

---

• Best sorting algorithm in terms of minimum swaps - Cycle Sort

---

• Most algorithms use merge sort in sorting in STLs but when input is small they use insertion sort