Introduction

Quick Sort is one of the fastest and most widely used sorting algorithms.

It is based on:

 Divide and Conquer

The idea is:

  1. Choose a pivot element
  2. Place pivot in correct position
  3. Move smaller elements left
  4. Move larger elements right
  5. Recursively sort both halves

This problem helps in understanding:

  • recursion
  • partitioning
  • divide and conquer
  • in-place sorting

Example

Input:arr = [10, 7, 8, 9, 1, 5]

Output:
[1, 5, 7, 8, 9, 10]

Explanation:
Pivot divides array into smaller and larger elements during every recursive call.

Constraints

 1 <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9

Approach : Divide and Conquer

Explanation

Quick Sort works in three steps:

  1. Choose Pivot
    • usually last element
  2. Partition Array
    • smaller elements left
    • larger elements right
  3. Recursively Sort
    • left half
    • right half

Partitioning is the key operation.

Steps

  1. Select pivot element.
  2. Partition array.
  3. Place pivot correctly.
  4. Recursively sort left side.
  5. Recursively sort right side.
  6. Return sorted array.

Dry Run

Input:[10, 7, 8, 9, 1, 5]

Pivot:
5

Partition:
[1] 5 [10, 7, 8, 9]

Pivot fixed at correct position

Recursively sort:
[1] and [10, 7, 8, 9]

Next pivot:
9

Partition:
[7, 8] 9 [10]

Continue recursion...

Final Result:
[1, 5, 7, 8, 9, 10]

Quick Sort Code

Complexity Analysis

ort helps in understan

Best Case Time Complexity: O(n log n)
Average Case Time Complexity: O(n log n)

Worst Case Time Complexity: O(n²)

Explanation:
Worst case occurs when pivot selection becomes poor.

Space Complexity: O(log n)
Explanation:
Recursive stack space is used.

Edge Cases

  1. Empty array
  2. Single element array
  3. Already sorted array
  4. Reverse sorted array
  5. Duplicate elements present

Why This Problem is Important

Quick Sort helps in understanding:

  1. Divide and Conquer
  2. Partitioning techniques
  3. Recursion
  4. In-place sorting
  5. Pivot optimization

It is one of the most important advanced sorting algorithms.

Real-World Applications

Quick Sort concepts are used in:

  1. Standard library sorting
  2. Database systems
  3. Search engines
  4. Large-scale data processing
  5. Operating systems

Common Mistakes

  1. Incorrect partition logic
  2. Wrong pivot placement
  3. Infinite recursion
  4. Incorrect recursive boundaries

Interview Tips

Interviewers often expect:

  1. Partition explanation
  2. Divide and Conquer understanding
  3. Average vs worst case analysis

Always explain:

  • pivot selection
  • partition process
  • recursive sorting separately

Related Questions

  1. Merge Sort
  2. Heap Sort
  3. Kth Largest Element
  4. Sort Colors
  5. Quick Select

Final Takeaway

Quick Sort is a fundamental divide-and-conquer sorting algorithm that teaches partitioning and recursive sorting techniques. Understanding Quick Sort builds a strong foundation for advanced sorting algorithms and interview problems.