Quick Sort Algorithm – Step by Step Explanation with Example and Time Complexity

Introduction

Quick Sort is one of the fastest and most widely used sorting algorithms in Data Structures. It also follows the Divide and Conquer approach, just like Merge Sort.

Quick Sort is popular because:

• It is very fast in practical situations

• It works efficiently for large datasets

• It is used in many programming libraries

In this article, we will understand:

• What is Quick Sort

• How it works step by step

• Example

• Time complexity

• Comparison with Merge Sort

• Advantages and disadvantages

• Exam questions

---

What is Quick Sort?

Quick Sort is a sorting algorithm that:

1. Selects a pivot element

2. Partitions the array around the pivot

3. Places smaller elements on left

4. Places larger elements on right

5. Recursively sorts both sides

The pivot element ends up in its correct position.

---

How Quick Sort Works (Step-by-Step Example)

Let’s take this array:

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

---

Step 1: Choose Pivot

Choose last element as pivot.

Pivot = 5

---

Step 2: Partition

Arrange elements:

Smaller than 5 → Left
Greater than 5 → Right

After partition:

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

Now 5 is in correct position.

---

Step 3: Recursively Apply Quick Sort

Left side:

[1]

Right side:

[8, 9, 10, 7]

Repeat process.

---

Final Sorted Array:

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

---

Time Complexity of Quick Sort

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n²)

Worst case happens when pivot selection is poor (already sorted array).

---

Why Quick Sort is Fast

Even though worst case is O(n²),
in practice Quick Sort is usually very fast because:

• Good pivot selection

• Efficient memory usage

• Cache-friendly

That is why it is used in real-world systems.

---

Space Complexity

Quick Sort uses:

👉 O(log n) space (due to recursion)

It does not require extra array like Merge Sort.

---

Quick Sort vs Merge Sort

Feature	Quick Sort	Merge Sort
Time (Average)	O(n log n)	O(n log n)
Worst Case	O(n²)	O(n log n)
Space	O(log n)	O(n)
Stable	No	Yes
Faster in practice	Yes	Moderate

Quick Sort is usually faster in memory-limited systems.

---

Real-Life Applications

Quick Sort is used in:

• Programming language libraries

• Database sorting

• System-level sorting

• Competitive programming

• Real-time applications

• Advantages of Quick Sort

• ✔ Very fast in average case
  ✔ Efficient memory usage
  ✔ In-place sorting
  ✔ Widely used

  ---

  Disadvantages of Quick Sort

  ❌ Worst case O(n²)
  ❌ Not stable
  ❌ Recursive implementation

  ---

  Why It Is Important for Exams

  In exams, remember:

  • Quick Sort uses Divide and Conquer

  • Pivot element is key concept

  • Average time = O(n log n)

  • Worst time = O(n²)

  • Compare with Merge Sort

  Quick Sort is one of the most frequently asked algorithms in university exams and interviews.

  ---

  Pseudocode (Exam Friendly)

  QuickSort(arr, low, high):
      if low < high:
          pi = Partition(arr, low, high)
          QuickSort(arr, low, pi-1)
          QuickSort(arr, pi+1, high)
  

  ---

  Conclusion

  Quick Sort is one of the most powerful and efficient sorting algorithms. Its average O(n log n) performance makes it suitable for large datasets.

  Although its worst case is O(n²), proper pivot selection makes it extremely efficient in practice.

  Understanding Quick Sort is essential for data structures exams and programming interviews.