What types of sorting do you know and what are their time and memory complexities?

There are many sorting algorithms, here are the main ones with their time and space complexities:

• Bubble Sort

  • Time: O(n²) in the worst and average case
  • Space: O(1) (in-place sorting)

• Insertion Sort

  • Time: O(n²) in the worst case, O(n) in the best (almost sorted array)
  • Space: O(1)

• Selection Sort

  • Time: O(n²) in all cases
  • Space: O(1)

• Merge Sort

  • Time: O(n log n) in all cases
  • Space: O(n) (requires additional memory for merging)

• Quick Sort

  • Time: O(n log n) on average, O(n²) in the worst case (rare)
  • Space: O(log n) (recursive stack)

• Heap Sort

  • Time: O(n log n) in all cases
  • Space: O(1)

• Timsort — a hybrid sorting algorithm used in Python and Java

  • Time: O(n log n) on average and in the worst case
  • Space: O(n)

The choice of algorithm depends on data size, memory requirements, and stability of sorting (whether it preserves the order of equal elements). For example, Merge Sort is stable, Quick Sort is usually faster but unstable.