# Sorting Algorithms

{% file src="/files/kmlILF7eX2KL9dRSQO5d" %}

Some of the most common sorting algorithms in C++ include:

* <mark style="color:blue;">**`Bubble sort:`**</mark> This simple sorting algorithm works by repeatedly comparing adjacent elements in an array and swapping them if they are in the wrong order. Bubble sort is not very efficient, but it is easy to implement.
* <mark style="color:blue;">**`Selection sort:`**</mark> This sorting algorithm works by repeatedly finding the smallest element in an array and swapping it with the first element. Selection sort is more efficient than bubble sort, but it is still *not very efficient for large arrays*.
* <mark style="color:blue;">**`Insertion sort:`**</mark> This sorting algorithm works by repeatedly inserting elements into their correct position in an array. Insertion sort is more efficient than bubble sort and selection sort, but it is still not very efficient for large arrays.
* <mark style="color:blue;">**`Merge sort:`**</mark> This sorting algorithm works by recursively splitting an array in half and merging the two halves back together in sorted order. Merge sort is very efficient for large arrays, but it is more complex to implement than the other sorting algorithms mentioned above.
* <mark style="color:blue;">**`Quick sort:`**</mark> This sorting algorithm works by choosing a pivot element in an array and partitioning the array around the pivot element. Quick sort is very efficient for large arrays, and it is also relatively easy to implement.

The best sorting algorithm to use in a particular situation depends on the size of the array and the desired level of efficiency. For small arrays, *bubble sort or selection sort* may be sufficient. For large arrays, *merge sort or quick sort* may be a better choice.

Here is a table that summarizes the `time complexity` of the sorting algorithms mentioned above:

<table><thead><tr><th width="160">Algorithm</th><th width="231">Best case(Already sorted array )</th><th width="121">Worst case</th><th>Average case(Reversed array)</th></tr></thead><tbody><tr><td><a href="/pages/m17cwn3ykSXKUBCCxSOG"><em><strong>Bubble sort</strong></em></a></td><td>O(n)</td><td>O(n^2)</td><td>O(n^2)</td></tr><tr><td><a href="/pages/vub11r0FZZYAZfQwwnZO"><em><strong>Selection sort</strong></em></a></td><td>O(n^2)</td><td>O(n^2)</td><td>O(n^2)</td></tr><tr><td><a href="/pages/cCLAxIX7Y3ZgGqK3w4WE"><em><strong>Insertion sort</strong></em></a></td><td>O(n)</td><td>O(n^2)</td><td>O(n^2)</td></tr><tr><td><a href="/pages/9Y6VgkmB3pTyGHNvSBO5"><em><strong>Merge sort</strong></em></a></td><td>O(n log n)</td><td>O(n log n)</td><td>O(n log n)</td></tr><tr><td><a href="/pages/J73yh8NAitY602XQ73iX"><em><strong>Quick sort</strong></em></a></td><td>O(n log n)</td><td>O(n^2)</td><td>O(n log n)</td></tr></tbody></table>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/sorting-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.