Sorting techniques with time complexity: Bubble sort,

Insertion sort, Merge sort, Quick sort

Bubble Sort in Data Structure (With Examples & Code)

Introduction

Sorting algorithms play a crucial role in organizing data efficiently in

computer science. Among these, Bubble Sort is a fundamental method used
widely for sorting of different data structures.

Let’s learn everything about Bubble Sort with examples, characteristics, and
practical applications.

What is Bubble Sort?

Bubble Sort is a simple way to sort a list of items, like numbers or letters, in
order. The basic idea is to repeatedly step through the list, compare each
pair of adjacent items, and swap them if they are in the wrong order. This
process is repeated until no more swaps are needed, meaning the list is
sorted.

Real-World Analogy of How Bubble Sort Works

Imagine you have a line of people standing in a row, and you want to arrange
them from shortest to tallest.

You start by comparing the first two people. If the first person is taller, they
swap places with the second person. Then, you move to the next pair and
compare them, swapping if needed. You keep doing this until you reach the
end of the line.

Then, you start over from the beginning. After each pass through the line,
the tallest person moves to the end. You continue this process until no more
swaps are needed, and everyone is standing in the correct order from
shortest to tallest.

This is how Bubble Sort works.

Bubble Sort Algorithm

1. Start at the beginning of the list.

2. Compare each pair of adjacent elements.

3. If the elements are in the wrong order, swap them.

4. Move to the next pair and repeat step 3 until the end of the list.
 5. After each pass through the list, the largest element moves to its
correct position.

6. Repeat the process for the remaining elements (excluding the last
sorted elements) until no swaps are needed.

Bubble Sort Example (Step by Step)

Let's sort the list [4, 2, 7, 1] using Bubble Sort.

1. Initial List

[4, 2, 7, 1]

2. First Pass

 Compare 4 and 2. Since 4 > 2, swap them: [2, 4, 7, 1]

 Compare 4 and 7. No swap needed as 4 < 7: [2, 4, 7, 1]

 Compare 7 and 1. Since 7 > 1, swap them: [2, 4, 1, 7]

List after the first pass: [2, 4, 1, 7]

3. Second Pass

 Compare 2 and 4. No swap needed as 2 < 4: [2, 4, 1, 7]

 Compare 4 and 1. Since 4 > 1, swap them: [2, 1, 4, 7]

 Compare 4 and 7. No swap needed as 4 < 7: [2, 1, 4, 7]

List after the second pass: [2, 1, 4, 7]

4. Third Pass

 Compare 2 and 1. Since 2 > 1, swap them: [1, 2, 4, 7]

 Compare 2 and 4. No swap needed as 2 < 4: [1, 2, 4, 7]

 Compare 4 and 7. No swap needed as 4 < 7: [1, 2, 4, 7]

List after the third pass: [1, 2, 4, 7]

5. Fourth Pass

 Compare 1 and 2. No swap needed as 1 < 2: [1, 2, 4, 7]

 Compare 2 and 4. No swap needed as 2 < 4: [1, 2, 4, 7]

 Compare 4 and 7. No swap needed as 4 < 7: [1, 2, 4, 7]

List after the fourth pass: [1, 2, 4, 7]

Since no swaps were needed in the fourth pass, the list is sorted. The final
sorted list is [1, 2, 4, 7].

This step-by-step process shows how Bubble Sort repeatedly goes through
the list, compares adjacent elements, and swaps them if needed, until the
entire list is sorted.

Characteristics of Bubble Sort

 Stability: Bubble Sort is stable; it maintains the relative order of equal

elements in the sorted output.

 In-place Sorting: Bubble Sort is an in-place algorithm; it requires only

a constant amount of additional memory.

 Adaptive Nature: Bubble Sort is adaptive; it performs well on nearly

sorted lists with a best-case time complexity of O(n).

Bubble Sort Pseudo Code

function bubbleSort(arr):

n = length(arr)

for i from 0 to n-1:

for j from 0 to n-i-2:

if arr[j] > arr[j+1]:

swap(arr[j], arr[j+1])

Implementation of Bubble Sort in Programming

We will see the implementation of bubble sort in C, C++, Java, and Python
below:

Bubble Sort in C

Below is the bubble sort in C program:

#include <stdio.h>

void bubbleSort(int arr[], int n) {

for (int i = 0; i < n-1; i++) {

for (int j = 0; j < n-i-1; j++) {

if (arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {

 printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {4, 2, 7, 1};

int n = sizeof(arr)/sizeof(arr[0]);

bubbleSort(arr, n);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

Bubble Sort in C++

Below is the bubble sort in C++ program:

#include <iostream>

using namespace std;

void bubbleSort(int arr[], int n) {

for (int i = 0; i < n-1; i++) {

for (int j = 0; j < n-i-1; j++) {

if (arr[j] > arr[j+1]) {

swap(arr[j], arr[j+1]);

}
void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {

cout << arr[i] << " ";

cout << endl;

int main() {

int arr[] = {4, 2, 7, 1};

int n = sizeof(arr)/sizeof(arr[0]);

bubbleSort(arr, n);

cout << "Sorted array: \n";

printArray(arr, n);

return 0;

Bubble Sort in Java

Below is the bubble sort in Java program:

public class BubbleSort {

static void bubbleSort(int[] arr) {

int n = [Link];

for (int i = 0; i < n-1; i++) {

for (int j = 0; j < n-i-1; j++) {

if (arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;
 }

static void printArray(int[] arr) {

for (int j : arr) {

[Link](j + " ");

[Link]();

public static void main(String[] args) {

int[] arr = {4, 2, 7, 1};

bubbleSort(arr);

[Link]("Sorted array: ");

printArray(arr);

Bubble Sort in Python

Below is the bubble sort in Python program:

def bubble_sort(arr):

n = len(arr)

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

def print_array(arr):

for i in arr:

print(i, end=" ")

print()

if __name__ == "__main__":

arr = [4, 2, 7, 1]

bubble_sort(arr)

print("Sorted array:")

print_array(arr)

Bubble Sort Time Complexity

Here is the time complexity of bubble sort in best case, worst case, and
average case:

Case Time
Complexity

Best Case O(n)

Average O(n2)
Case

Worst Case O(n2)

Bubble Sort Space Complexity

The space complexity of bubble sort is O(1).

Advantages and Disadvantages of Bubble Sort

Advantages

 Simple to Implement: Easy to understand and code.

 Stable: Maintains the relative order of equal elements.

  In-place Sorting: Requires only a constant amount of additional
memory.

 Adaptive: Efficient for nearly sorted lists with a best-case time

complexity of O(n).

Disadvantages

 Inefficient: Poor performance on large lists with an average and

worst-case time complexity of O(n2).

 High Number of Comparisons: Even if the list is partially sorted,

Bubble Sort makes unnecessary comparisons.

 Not Suitable for Large Datasets: Due to its quadratic time

complexity, it's not recommended for large datasets

Applications of Bubble Sort

 Educational Purposes: Ideal for teaching and learning basic sorting

algorithms.

 Small Datasets: Suitable for sorting small lists where simplicity is

more important than efficiency.

 Partially Sorted Data: Performs well on nearly sorted data, making it

useful in scenarios where data is mostly ordered.

 Computer Graphics: Sometimes used in simple graphics applications

where small arrays need sorting.

Insertion Sort:

Introduction

Insertion sorting algorithm is one of the fundamental techniques used in

computer science for arranging elements in a particular order. Understanding
this algorithm is essential for beginners learning data structures and
algorithms, as it forms the basis for more complex sorting methods.

What is Insertion Sort?

Insertion sort is a simple sorting algorithm that builds the final sorted array
one item at a time. It works by taking an element from the unsorted part of
the list and inserting it into its correct position in the sorted part. This
process is repeated until all elements are sorted.
Insertion sort is a way to sort a list of items. Imagine you have a deck of
cards and you want to sort them in your hand. You pick up one card at a time
and place it in the right spot among the cards you’ve already sorted.

How Insertion Sort Works?

 Pick an element: Start from the second element because the first
element is already sorted.

 Find the correct position: Compare the picked element with each
element in the sorted part of the array.

 Shift elements: Move all elements larger than the picked element one
position to the right.

 Insert the element: Place the picked element into the correct position.

 Repeat: Continue this process until all elements are sorted.

For example, if you start with one card, it’s already sorted. When you pick up
the next card, you compare it with the first card and place it either before or
after it, depending on its value. You keep doing this for each card you pick
up. Each new card is inserted into the correct position among the cards
you’ve already sorted.

This is exactly how insertion sort works with numbers or any other items. It
takes one item at a time and inserts it into the right position in the list,
making sure that the part of the list it has sorted so far is always in order. It’s
a simple and easy-to-understand method for sorting, just like sorting cards in
your hand.

Insertion Sorting Algorithm

Let’s understand the algorithm for insertion sort in data structure:

 Pseudocode for Insertion Sort

Insertion Sort(array)

for i from 1 to length(array) - 1 do

key = array[i]

j=i-1

while j >= 0 and array[j] > key do

array[j + 1] = array[j]
 j=j-1

array[j + 1] = key

1. Initialization

 for i from 1 to length(array) - 1 do: The algorithm of insertion sort

starts from the second element (index 1) and iterates through the
entire array. This is because the first element is already considered
sorted.

2. Key Selection

 key = array[i]: The current element array[i] is stored in the variable

key. This is the element that will be inserted into the correct position in
the sorted part of the array.

3. Comparison and Shifting

 j = i - 1: Initialize j to the index of the last element in the sorted part of

the array.

 while j >= 0 and array[j] > key do: Compare the key with each element
in the sorted part, starting from the rightmost element (array[j]).

 array[j + 1] = array[j]: If the current element array[j] is greater than

key, shift array[j] one position to the right.

 j = j - 1: Move to the next element to the left (j is decremented by 1).

4. Insertion

array[j + 1] = key: Once the correct position is found (when array[j] is no

longer greater than key or j is less than 0), insert the key into that position.
The correct position is j + 1 because j was decremented one extra time in
the previous loop.

Insertion Sort Example

Let's sort the array [4, 3, 2, 10, 12, 1, 5, 6] using insertion sorting algorithm.

Start with first element:

[4, 3, 2, 10, 12, 1, 5, 6]

Pick 3, compare with 4, and insert before 4:

[3, 4, 2, 10, 12, 1, 5, 6]

Pick 2, compare with 4 and 3, insert before 3:

[2, 3, 4, 10, 12, 1, 5, 6]

Pick 10, compare with 4, stays in place:

[2, 3, 4, 10, 12, 1, 5, 6]

Pick 12, compare with 10, stays in place:

[2, 3, 4, 10, 12, 1, 5, 6]

Pick 1, compare with 12, 10, 4, 3, 2, insert before 2:

[1, 2, 3, 4, 10, 12, 5, 6]

Pick 5, compare with 12, 10, 4, insert after 4:

[1, 2, 3, 4, 5, 10, 12, 6]

Pick 6, compare with 12, 10, insert after 5:

[1, 2, 3, 4, 5, 6, 10, 12]

After these steps, the array is sorted: [1, 2, 3, 4, 5, 6, 10, 12].

Insertion Sort in Python

def insertion_sort(arr):

for i in range(1, len(arr)):

key = arr[i]

j=i-1

while j >= 0 and key < arr[j]:

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = key

return arr

# Example usage

arr = [12, 11, 13, 5, 6]

print("Sorted array is:", insertion_sort(arr))

Insertion Sort Program in C Language

#include <stdio.h>

void insertionSort(int arr[], int n) {

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);

printf("Sorted array is: ");

 printArray(arr, n);

return 0;

Insertion Sort in C++

#include <iostream>

using namespace std;

void insertionSort(int arr[], int n) {

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

cout << endl;

int main() {
 int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);

cout << "Sorted array is: ";

printArray(arr, n);

return 0;

Insertion Sort Using Java

public class InsertionSort {

public static void insertionSort(int[] arr) {

int n = [Link];

for (int i = 1; i < n; ++i) {

int key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

public static void printArray(int[] arr) {

for (int i : arr) {

[Link](i + " ");

}
 [Link]();

public static void main(String[] args) {

int[] arr = {12, 11, 13, 5, 6};

insertionSort(arr);

[Link]("Sorted array is:");

printA}rray(arr);

Time Complexity of Insertion Sort

Case Time
Complexity

Best Case O(n)

Average O(n^2)
Case

Worst O(n^2)
Case

Space Complexity of Insertion Sort

The space complexity of insertion sort is O(1). It means that this sorting
algorithm requires a constant amount of additional memory space.

Advantages and Disadvantages of Insertion Sort

Now, we will know about both the pros and cons of insertion sorting
algorithm:

Insertion Sort Advantages

 Easy to understand and implement compared to other complex sorting

algorithms.

 Performs well for small arrays or lists due to low overhead.

  Efficient for data that is already substantially sorted. In the best case
(when the array is already sorted), the time complexity is O(n).

 Maintains the relative order of records with equal keys (i.e., it does not
change the order of equal elements).

 Requires only a constant amount (O(1)) of additional memory space, as

it sorts the array in place.

 Can sort a list as it receives it. This means it can sort data dynamically
as new data comes in.

Insertion Sort Disadvantages

 The time complexity of O(n^2) makes it inefficient for large lists

or arrays compared to more advanced algorithms like Quick
Sort, Merge Sort, or Heap Sort.

 Requires more comparisons and shifts in the worst case (when the
array is sorted in reverse order), which can be time-consuming.

 For large datasets or when performance is critical, other sorting

algorithms are generally more suitable.

 Due to the frequent shifting of elements, it may not perform well with
cache memory in comparison to algorithms like Quick Sort.

Applications of Insertion Sorting Algorithm

 Small Data Sets: Efficient for sorting small lists or arrays due
to its low overhead.

 Partially Sorted Data: Ideal for arrays that are already partially
sorted, as it can quickly finish the sorting.

 Real-Time Systems: Useful in systems where the data is

continuously received and needs to be sorted in real-time.

 Adaptive Sorting: Employed in situations where the data is

nearly sorted or when new elements are frequently added to a
sorted array.

 Educational Purposes: Often used in teaching fundamental

sorting concepts and algorithms due to its simplicity.
  Hybrid Sorting Algorithms: Used as a part of more complex
algorithms like Timsort, which combines insertion sort
with merge sort for improved performance on real-world data.

Merge Sort: Algorithm, Example, Complexity, Code

Introduction

The merge sort algorithm is a fundamental technique in computer science

for arranging elements in order. Understanding the merge sort algorithm is
crucial for beginners learning data structures and algorithms, as it provides a
basis for more advanced sorting methods.

What is Merge Sort?

Merge sort is a way to sort a list of items, like numbers or names, in order.
Imagine you have a big pile of mixed-up playing cards, and you want to sort
them. You can break the pile into smaller groups, sort each group, and then
put the groups back together in order.

For example, if you have two sorted lists, like [3, 8] and [2, 7], you compare
the first items in each list. Since 2 is smaller than 3, you put 2 in the new list
first. Then you compare 3 and 7. Since 3 is smaller, you add 3 next. You keep
doing this until all items are merged into one sorted list.

Merge Sort Example

Let’s understand merge sort algorithm with example:

We will sort the array [38, 27, 43, 3, 9, 82, 10] using merge sort.

1. Divide the Array

The array is divided into two halves.

2. Divide Each Half

Continue dividing each half into smaller subarrays until each

subarray has only one element.

3. Merge Each Pair of Subarrays

Now, start merging the subarrays back together in sorted order.

 Merge [38] and [27] to get [27, 38].

 Merge [43] and [3] to get [3, 43].

  Merge [9] and [82] to get [9, 82].

[27, 38] [3, 43] [9, 82] [10]

4. Merge the Sorted Subarrays

Continue merging the sorted subarrays.

 Merge [27, 38] and [3, 43] to get [3, 27, 38, 43].

 Merge [9, 82] and [10] to get [9, 10, 82].

[3, 27, 38, 43] [9, 10, 82]

5. Merge the Final Two Halves

Finally, merge the last two halves to get the fully sorted array.

Merge [3, 27, 38, 43] and [9, 10, 82].

 Start by comparing the first elements of each half: 3 (left) and

9 (right). 3 is smaller, so add 3 to the new array.

 Next, compare 27 (left) and 9 (right). 9 is smaller, so add 9 to

the new array.

 Then, compare 27 (left) and 10 (right). 10 is smaller, so add 10

to the new array.

 Next, compare 27 (left) and 82 (right). 27 is smaller, so add 27

to the new array.

 Continue comparing and adding the smallest elements until all

elements are merged.

[3, 9, 10, 27, 38, 43, 82]

6. Final Sorted Array

The array is now fully sorted: [3, 9, 10, 27, 38, 43, 82].
Merge Sort Algorithm

We will now go throught the algorithm of merge sort with

pseudocode:

MergeSort(array)

if length(array) > 1 then

mid = length(array) // 2

leftHalf = array[0:mid]

rightHalf = array[mid:length(array)]

MergeSort(leftHalf)

MergeSort(rightHalf)
 i=j=k=0

while i < length(leftHalf) and j < length(rightHalf) do

if leftHalf[i] < rightHalf[j] then

array[k] = leftHalf[i]

i=i+1

else

array[k] = rightHalf[j]

j=j+1

k=k+1

while i < length(leftHalf) do

array[k] = leftHalf[i]

i=i+1

k=k+1

while j < length(rightHalf) do

array[k] = rightHalf[j]

j=j+1

k=k+1

1. Base Case Check

if length(array) > 1 then: Check if the array has more than one
element. If not, it is already sorted, and no further action is needed.

2. Divide the Array

 mid = length(array) // 2: Find the middle index of the array.

  leftHalf = array[0:mid]: Create the left half of the array from
the start to the middle.

 rightHalf = array[mid:length(array)]: Create the right half of

the array from the middle to the end.

3. Recursive Calls

 MergeSort(leftHalf): Recursively sort the left half of the array.

 MergeSort(rightHalf): Recursively sort the right half of the

array.

4. Initialize Indices

i = j = k = 0: Initialize indices for iterating through the left half (i),

right half (j), and the main array (k).

5. Merge the Halves

 while i < length(leftHalf) and j < length(rightHalf) do: Compare

elements from the left and right halves.

 if leftHalf[i] < rightHalf[j] then: If the element in the left half is

smaller, add it to the main array.

 array[k] = leftHalf[i]: Place the element from the left half into
the main array.

 i = i + 1: Move to the next element in the left half.

 else: If the element in the right half is smaller, add it to the

main array.

 array[k] = rightHalf[j]: Place the element from the right half

into the main array.

 j = j + 1: Move to the next element in the right half.

 k = k + 1: Move to the next position in the main array.

6. Copy Remaining Elements

 while i < length(leftHalf) do: If there are remaining elements in

the left half, copy them to the main array.

 array[k] = leftHalf[i]: Place the remaining element from the

left half into the main array.
  i = i + 1: Move to the next element in the left half.

 k = k + 1: Move to the next position in the main array.

 while j < length(rightHalf) do: If there are remaining elements

in the right half, copy them to the main array.

 array[k] = rightHalf[j]: Place the remaining element from the

right half into the main array.

 j = j + 1: Move to the next element in the right half.

 k = k + 1: Move to the next position in the main array.

Implementation of Merge Sort in Python

def merge_sort(arr):

if len(arr) > 1:

mid = len(arr) // 2

left_half = arr[:mid]

right_half = arr[mid:]

merge_sort(left_half)

merge_sort(right_half)

i=j=k=0

while i < len(left_half) and j < len(right_half):

if left_half[i] < right_half[j]:

arr[k] = left_half[i]

i += 1

else:

arr[k] = right_half[j]

j += 1
 k += 1

while i < len(left_half):

arr[k] = left_half[i]

i += 1

k += 1

while j < len(right_half):

arr[k] = right_half[j]

j += 1

k += 1

# Example usage

arr = [12, 11, 13, 5, 6, 7]

merge_sort(arr)

print("Sorted array is:", arr)

Implementation of Merge Sort in C

#include <stdio.h>

#include <stdlib.h>

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int L[n1], R[n2];

for (int i = 0; i < n1; i++)

 L[i] = arr[left + i];

for (int j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}
}

void mergeSort(int arr[], int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

void printArray(int A[], int size) {

for (int i = 0; i < size; i++)

printf("%d ", A[i]);

printf("\n");

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);
 return 0;

Implementation of Merge Sort in C++

#include <iostream>

using namespace std;

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int L[n1], R[n2];

for (int i = 0; i < n1; i++)

L[i] = arr[left + i];

for (int j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;
 }

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

void mergeSort(int arr[], int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

void printArray(int A[], int size) {

for (int i = 0; i < size; i++)

cout << A[i] << " ";

 cout << endl;

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";

printArray(arr, arr_size);

return 0;

Implementation of Merge Sort in Java

public class MergeSort {

public static void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int L[] = new int[n1];

int R[] = new int[n2];

for (int i = 0; i < n1; ++i)

L[i] = arr[left + i];

for (int j = 0; j < n2; ++j)

R[j] = arr[mid + 1 + j];

int i = 0, j = 0;

int k = left;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}
}

public static void mergeSort(int arr[], int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

public static void printArray(int arr[]) {

int n = [Link];

for (int i = 0; i < n; ++i)

[Link](arr[i] + " ");

[Link]();

public static void main(String args[]) {

int arr[] = {12, 11, 13, 5, 6, 7};

[Link]("Given array is");

printArray(arr);

mergeSort(arr, 0, [Link] - 1);

[Link]("\nSorted array is");

printArray(arr);
 }

Merge Sort Time Complexity

The time complexity of merge sort in best case is O(n log n). Below are time
complexities in all cases:

Case Time Explanation

Complexity

Best O(n log n) The array is always divided into halves, and
Case merging two halves takes linear time.

Average O(n log n) The array is always divided into halves, and
Case merging two halves takes linear time,
regardless of the input.

Worst O(n log n) The array is always divided into halves, and
Case merging two halves takes linear time,
regardless of the input.

Merge Sort Space Complexity

The space complexity of merge sort is O(n). It requires additional space

proportional to the size of the array for temporary subarrays during merging.

Advantages of Merge Sort

 Consistent Time Complexity: O(n log n) time complexity in all cases

(best, average, worst).

 Stable Sorting: Maintains the relative order of equal elements.

 Efficient for Large Data Sets: Handles large arrays or lists efficiently.

 Parallelizable: Can be easily parallelized due to its divide-and-conquer

nature.

 Predictable Performance: Performance does not degrade based on

input data characteristics.

Disadvantages of Merge Sort

 High Space Complexity: Requires O(n) additional space for merging.

  Complex Implementation: More complex to implement compared to
simpler algorithms like insertion sort or selection sort.

 Not In-Place: Uses extra space for temporary subarrays, which can be a
limitation for memory-constrained environments.

 Overhead for Small Arrays: For small arrays, the overhead of recursive
calls and merging can make it slower than simpler algorithms like
insertion sort.

Uses and Applications of Merge Sort

 Large Data Sets: Efficiently sorts large arrays or lists due to its O(n log
n) time complexity.

 External Sorting: Suitable for sorting large data sets that do not fit into
memory (e.g., external merge sort).

 Stable Sort Requirement: Used when maintaining the relative order of

equal elements is important.

 Linked Lists: Efficient for sorting linked lists, as it does not require
random access to elements.

 Parallel Processing: Can be easily parallelized, making it useful in multi-

threaded or distributed environments.

 Inversion Count Problems: Used in counting the number of inversions in

an array, a measure of how far the array is from being sorted.

Quick Sort: Algorithm, Time & Space Complexity, Code, Example

Introduction

Quick sort is one of the most widely used and efficient sorting algorithms.
Known for its speed and simplicity, the quick sort algorithm is a fundamental
concept for anyone learning DSA.

This algorithm efficiently organizes data by dividing and conquering, making

it a preferred choice in various applications.
What is Quick Sort?

Quick sort is a method used to arrange a list of items, like numbers, in order.
It works by selecting one item from the list, called the "pivot," and then
arranging the other items so that all the smaller items come before the pivot
and all the larger items come after it. This process is repeated for the smaller
groups of items until the entire list is sorted.

How Does Quick Sort Work?

 Pick a Pivot: Choose one item from the list. It can be any item, but
people often pick the middle item or the first one.

 Divide the List: Compare all the other items to the pivot. Put the items
smaller than the pivot on the left side and the items larger than the
pivot on the right side.

 Repeat: Now, do the same thing with the left side and the right side
separately. Pick new pivots and keep dividing the list until each group
has only one item left.

 Combine: Once all the small groups are sorted, you put them back
together to get the full, sorted list.

Quick Sort Example

Imagine you have a list of numbers like [8, 3, 7, 1, 9, 2].

Here’s how quick sort would work:

1. Pick a Pivot: Let’s choose 7 as the pivot.

2. Divide: Compare each number to 7:

 Numbers smaller than 7: [3, 1, 2]

 Numbers larger than 7: [8, 9]

Now, your list looks like this: [3, 1, 2], [7], [8, 9].

3. Repeat: Sort the smaller groups:

For [3, 1, 2], pick 3 as the pivot.

Compare:

 Numbers smaller than 3: [1, 2]

 Numbers larger than 3: []

Now, you have: [1, 2], [3], [7], [8, 9].

4. Combine: Put it all together: [1, 2, 3, 7, 8, 9].

And that’s your sorted list using quick sort!

Quick Sort Algorithm

Let’s understand the algorithm for quick sort:

 Pseudocode for Quick Sort Algorithm

QuickSort(arr, low, high)

if low < high then

pivot_index = Partition(arr, low, high)

QuickSort(arr, low, pivot_index - 1)

QuickSort(arr, pivot_index + 1, high)

Partition(arr, low, high)

 pivot = arr[high]

i = low - 1

for j from low to high - 1 do

if arr[j] <= pivot then

i=i+1

swap arr[i] with arr[j]

swap arr[i + 1] with arr[high]

return i + 1

1. QuickSort(arr, low, high)

This is the main function that implements Quick Sort.

 if low < high then:

The function checks if there are more than one elements in the
portion of the array being sorted. If low is less than high, it means
there are multiple elements to sort.

 pivot_index = Partition(arr, low, high):

The array is partitioned into two subarrays, one with elements less
than or equal to the pivot and the other with elements greater than
the pivot. The function returns the pivot's final position
(pivot_index).

 QuickSort(arr, low, pivot_index - 1):

The left subarray (from low to pivot_index - 1) is sorted recursively.

 QuickSort(arr, pivot_index + 1, high):

The right subarray (from pivot_index + 1 to high) is sorted

recursively.

2. Partition(arr, low, high)

This function rearranges the elements in the array so that all

elements less than or equal to the pivot are on the left, and all
elements greater than the pivot are on the right.

 pivot = arr[high]:
The last element of the array (or subarray) is chosen as the pivot.

 i = low - 1:

The pointer i is initialized to one position before the start of the

array (or subarray).

 for j from low to high - 1 do:

Iterate through each element in the array (or subarray) from low to
high - 1.

 if arr[j] <= pivot then:

If the current element arr[j] is less than or equal to the pivot,

increment the pointer i and swap arr[i] with arr[j].

 swap arr[i] with arr[j]:

Swap the current element arr[j] with the element at the ith position,
ensuring that smaller elements are moved to the left.

 swap arr[i + 1] with arr[high]:

After the loop, swap the pivot element with the element at i + 1 to
place the pivot in its correct position.

return i + 1:

The function returns the index of the pivot, which is now in its
correct sorted position.

Quick Sort in Python

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr) // 2]

left = [x for x in arr if x < pivot]

middle = [x for x in arr if x == pivot]

right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

# Example usage

arr = [3, 6, 8, 10, 1, 2, 1]

sorted_arr = quick_sort(arr)

print("Sorted array is:", sorted_arr)

Quick Sort Algorithm in C

Here is a quick sort program in C language:

#include <stdio.h>

void swap(int* a, int* b) {

int t = *a;

*a = *b;

*b = t;

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] < pivot) {

i++;

swap(&arr[i], &arr[j]);

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}
void quick_sort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quick_sort(arr, low, pi - 1);

quick_sort(arr, pi + 1, high);

// Example usage

int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

quick_sort(arr, 0, n - 1);

printf("Sorted array: \n");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

printf("\n");

return 0;

Quick Sort in C++

#include <iostream>

using namespace std;

void swap(int* a, int* b) {

 int t = *a;

*a = *b;

*b = t;

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] < pivot) {

i++;

swap(&arr[i], &arr[j]);

swap(&arr[i + 1], &arr[high]);

return (i + 1);

void quick_sort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quick_sort(arr, low, pi - 1);

quick_sort(arr, pi + 1, high);

}
// Example usage

int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

quick_sort(arr, 0, n - 1);

cout << "Sorted array: \n";

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";

cout << endl;

return 0;

Quick Sort in Java

public class QuickSort {

public static void quickSort(int[] arr, int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

public static int partition(int[] arr, int low, int high) {

int pivot = arr[high];

 int i = (low - 1);

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {

i++;

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

int temp = arr[i + 1];

arr[i + 1] = arr[high];

arr[high] = temp;

return i + 1;

// Example usage

public static void main(String[] args) {

int[] arr = {10, 7, 8, 9, 1, 5};

int n = [Link];

quickSort(arr, 0, n - 1);

[Link]("Sorted array:");

for (int i = 0; i < n; i++) {

[Link](arr[i] + " ");

}
Quick Sort Time Complexity

Here is the time complexity of quick sort:

Case Time
Complexity

Best Case O(n log n)

Average O(n log n)

Case

Worst O(n^2)
Case

 n: Number of elements in the input array.

Quick Sort's best and average-case time complexity is O(n log n) due to the
divide-and-conquer approach, where the array is recursively partitioned. The
worst-case time complexity of O(n^2) happens when the pivot choice leads
to unbalanced partitions, such as when the array is already sorted or when
the pivot is consistently the smallest or largest element.

Space Complexity of Quick Sort

Space Explanation
Complexity

O(log n) Space complexity for the recursive call stack in the

best and average cases, where the array is evenly
partitioned.

O(n) Space complexity in the worst case, where the array

 is highly unbalanced, leading to deep recursion.

Advantages of Quick Sort

 Efficient Average Case: O(n log n) time complexity on average, making

it faster for most inputs.

 In-Place Sorting: Requires minimal additional memory, typically O(log

n) space.

 Widely Used: Commonly used in practice due to its efficiency and

simplicity.

 Divide and Conquer: Effectively handles large datasets by breaking

them into smaller subproblems.

Disadvantages of Quick Sort

 Worst-Case Performance: Can degrade to O(n²) time complexity if the

pivot choices are poor (e.g., when the array is already sorted).

 Not Stable: Does not preserve the relative order of equal elements
unless modified.

 Recursive Overhead: Recursive nature can lead to stack overflow for

large arrays or deep recursion, especially in the worst case.

 Performance Depends on Pivot Selection: Choosing an optimal pivot is

crucial; poor choices can significantly impact performance.

Applications of Quick Sort

 s.

 Database Query Optimization: Used in database systems to optimize

query processing by efficiently sorting large datasets.

 Search Algorithms: Helps in efficient searching by sorting data

beforehand.

 Memory-Constrained Environments: Suitable for in-place sorting where

memory usage needs to be minimized.

 Real-Time Systems: Quick execution time makes it useful in systems

requiring fast response times.

 Parallel Algorithms: Can be parallelized effectively, making it suitable

for high-performance computing tasks.
  Algorithm Education: Widely taught in computer science courses as an
example of an efficient, comparison-based sorting algorithm.

Searching techniques with time Complexity: Linear

search and Binary search
Introduction

Linear search and binary search are two fundamental search algorithms used
in computer science. While both are designed to find a specific element in a
list or array, they differ significantly in how they operate and their efficiency.

Linear search checks each element one by one until it finds the target,
making it simple but slower for large datasets. On the other hand, the binary
search algorithm efficiently narrows down the search range by repeatedly
dividing the list in half, but it requires the data to be sorted.

Here, we will learn the difference between linear search and binary search
with example.

What is Linear Search?

Linear search is a straightforward searching algorithm used to find the

position of a target element within a list or array. The basic idea is to start at
the beginning of the list and check each element one by one until the target
element is found or the end of the list is reached.

If the element is found, the algorithm returns its position; if not, it returns a
signal that the element is not present (often -1 or None).

How Linear Search Works?

Linear search operates by iterating through the list from the first element to
the last. It compares each element with the target value:

 Start at the first element.

 Compare the target element with the current element.

 If they match, return the index of the current element.

 If they do not match, move to the next element.

  Repeat this process until the target element is found or the end of the
list is reached.

Since it checks each element in sequence, the worst-case scenario is that the
algorithm has to check every element in the list, making its time
complexity O(n), where n is the number of elements in the list.

Example of Linear Search

Imagine you have a list of numbers: [5, 8, 1, 3, 7, 9, 2] and you want to find
the position of the number 7.

Step 1: Start with the first element, 5. Compare it with 7. Since 5 is not 7,
move to the next element.

Step 2: Compare the next element, 8, with 7. Again, it's not a match, so
move to the next element.

Step 3: Continue this process with 1, 3, until you reach 7.

Step 4: When you reach 7, it's a match! The algorithm returns the position
of 7 in the list, which is 4 (if you start counting from 0).

If 7 was not in the list, the algorithm would check all the elements and return
-1 or None, indicating that the target element is not present.

Advantages of Linear Search

 Easy to understand and implement, requiring no

complex algorithms or data structures.
  Can be used on both unsorted and unsorted lists, making it versatile
for various scenarios.

 No need to sort the data before searching, which saves time in

scenarios where the data is frequently changing.

 Can be applied to arrays, linked lists, and other data structures

without modification.

Disadvantages of Linear Search

 Time complexity is O(n), making it slow and inefficient for large

datasets, especially if the element is near the end or not present at all.

 Even if the data is sorted, Linear Search doesn’t take advantage of this,
resulting in potentially unnecessary comparisons.

 Requires checking each element sequentially, which can be slow

compared to more advanced search algorithms.

Linear Search Implementation

Python

def linear_search(arr, target):

for i in range(len(arr)):

if arr[i] == target:

return i

return -1

# Example usage

arr = [2, 4, 0, 1, 9]

target = 1

result = linear_search(arr, target)

if result != -1:

print(f"Element found at index {result}")

else:
 print("Element not found")

#include <stdio.h>

int linear_search(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {

if (arr[i] == target) {

return i;

return -1;

// Example usage

int main() {

int arr[] = {2, 4, 0, 1, 9};

int target = 1;

int n = sizeof(arr) / sizeof(arr[0]);

int result = linear_search(arr, n, target);

if (result != -1) {

printf("Element found at index %d\n", result);

} else {

printf("Element not found\n");

return 0;

C++
#include <iostream>

using namespace std;

int linear_search(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {

if (arr[i] == target) {

return i;

return -1;

// Example usage

int main() {

int arr[] = {2, 4, 0, 1, 9};

int target = 1;

int n = sizeof(arr) / sizeof(arr[0]);

int result = linear_search(arr, n, target);

if (result != -1) {

cout << "Element found at index " << result << endl;

} else {

cout << "Element not found" << endl;

return 0;

Java

public class LinearSearch {

 public static int linearSearch(int[] arr, int target) {

for (int i = 0; i < [Link]; i++) {

if (arr[i] == target) {

return i;

return -1;

// Example usage

public static void main(String[] args) {

int[] arr = {2, 4, 0, 1, 9};

int target = 1;

int result = linearSearch(arr, target);

if (result != -1) {

[Link]("Element found at index " + result);

} else {

[Link]("Element not found");

What is Binary Search?

Binary search is an efficient search algorithm used to find the position of a

target element within a sorted list or array. Unlike linear search, which
checks each element one by one, binary search works by repeatedly dividing
the search interval in half.
The key requirement for binary search is that the list must be sorted. This
allows the algorithm to eliminate half of the remaining elements in each
step, making it much faster than linear search for large datasets.

The time complexity of binary search is O(log n), where n is the number of
elements in the list.

How Binary Search Works?

Binary search operates by following these steps:

Step 1: Initialize Search Range

Start by setting two pointers: low at the beginning of the list and high at the
end.

Step 2: Find the Middle Element

 Calculate the middle index of the current search range: middle = (low
+ high) // 2.

 Compare the middle element with the target element.

Step 3: Compare and Narrow the Search Range

 If the middle element matches the target, return the middle index.

 If the target element is less than the middle element, narrow the
search to the left half by setting high = middle - 1.

 If the target element is greater than the middle element, narrow the
search to the right half by setting low = middle + 1.

Step 4: Repeat

Repeat steps 2 and 3 until the target element is found or the search range
becomes invalid (i.e., low > high).

Step 5: Target Not Found

If the target element is not found after the search range is invalid, return a
signal (e.g., -1 or None) indicating that the target is not present in the list.

Example of Binary Search

Imagine you have a sorted list of numbers: [1, 3, 5, 7, 9, 11, 13] and you
want to find the position of the number 9.

Step 1: Initialize Search Range

low = 0 (points to 1), high = 6 (points to 13).

Step 2: Find the Middle Element

 Calculate middle = (0 + 6) / 2 = 3 (points to 7).

 Compare 7 with 9. Since 7 is less than 9, narrow the search range to

the right half.

Step 3: Narrow the Search Range:

 Set low = 4 (points to 9), keeping high = 6 (points to 13).

 Calculate middle = (4 + 6) // 2 = 5 (points to 11).

 Compare 11 with 9. Since 11 is greater than 9, narrow the search

range to the left half.

Step 4: Narrow Further

 Set high = 4 (points to 9), keeping low = 4 (also points to 9).

 Calculate middle = (4 + 4) // 2 = 4 (points to 9).

 Compare 9 with 9. Since they match, return the index 4.

Binary search finds the target element 9 in the list at index 4. Because it
eliminates half of the search space with each comparison, binary search is
much more efficient than linear search for large, sorted lists.
Advantages of Binary Search

 Time complexity is O(log n), making it much faster than Linear Search
for large datasets, especially when the data is sorted.

 Takes full advantage of sorted data, halving the search space with each
step, which drastically reduces the number of comparisons needed.

 Performs well on large datasets, maintaining efficiency even as the

dataset size grows.

Disadvantages of Binary Search

 The list or array must be sorted before applying Binary Search, which
adds an extra step and can be time-consuming if the data isn’t already
sorted.

 More complex to implement and understand than Linear Search,

especially when dealing with recursive implementations.

 Cannot be applied directly to unsorted data, limiting its versatility in

scenarios where the dataset is frequently updated or unsorted.
  The recursive version of Binary Search has O(log n) space complexity
due to the stack space used by recursive calls.

Binary Search Implementation

Python

def binary_search(arr, target):

low = 0

high = len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

# Example usage

arr = [1, 3, 5, 7, 9, 11, 13]

target = 7

result = binary_search(arr, target)

if result != -1:

print(f"Element found at index {result}")

else:

print("Element not found")

C

#include <stdio.h>

int binary_search(int arr[], int n, int target) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {

return mid;

} else if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

return -1;

// Example usage

int main() {

int arr[] = {1, 3, 5, 7, 9, 11, 13};

int target = 7;

int n = sizeof(arr) / sizeof(arr[0]);

int result = binary_search(arr, n, target);

 if (result != -1) {

printf("Element found at index %d\n", result);

} else {

printf("Element not found\n");

return 0;

C++

#include <iostream>

using namespace std;

int binary_search(int arr[], int n, int target) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {

return mid;

} else if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

return -1;
}

// Example usage

int main() {

int arr[] = {1, 3, 5, 7, 9, 11, 13};

int target = 7;

int n = sizeof(arr) / sizeof(arr[0]);

int result = binary_search(arr, n, target);

if (result != -1) {

cout << "Element found at index " << result << endl;

} else {

cout << "Element not found" << endl;

return 0;

Java

public class BinarySearch {

public static int binarySearch(int[] arr, int target) {

int low = 0;

int high = [Link] - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {

return mid;
 } else if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

return -1;

// Example usage

public static void main(String[] args) {

int[] arr = {1, 3, 5, 7, 9, 11, 13};

int target = 7;

int result = binarySearch(arr, target);

if (result != -1) {

[Link]("Element found at index " + result);

} else {

[Link]("Element not found");

Linear and Binary Search: Time Complexity

Algorithm Best Average Worst

Case Case Case
Linear O(1) O(n) O(n)
Search

Binary O(1) O(log n) O(log n)

Search

Linear Search Time Complexity

 Best Case: O(1) occurs when the target element is the first element in
the list.

 Average Case: O(n) occurs when the target element is in the middle
or when we don't know where the element is located.

 Worst Case: O(n) occurs when the target element is the last element
in the list or not present at all.

Binary Search Time Complexity

 Best Case: O(1) occurs when the target element is the middle
element of the list.

 Average Case: O(log n) occurs as the list is repeatedly divided in half.

 Worst Case: O(log n) occurs when the target element is either very
small or very large, requiring the maximum number of divisions.

Linear Search vs. Binary Search: Space Complexity

Algorithm Space
Complexity

Linear O(1)
Search

Binary O(1) (Iterative)

Search
or

O(log n)
(Recursive)
Linear Search Space Complexity

Space complexity of linear search is O(1) because it only requires a

constant amount of additional memory, regardless of the size of the input
array.

Binary Search Space Complexity

 O(1) in its iterative form, as it only uses a few extra variables.

 O(log n) in its recursive form, due to the memory required for the
recursive call stack.

Algorithm of Linear Search and Binary Search

Pseudocode for Linear Search:

LinearSearch(arr, target):

for i from 0 to length of arr - 1 do:

if arr[i] == target:

return i // Target found, return index

return -1 // Target not found

Pseudocode for Binary Search (Iterative)

BinarySearch(arr, target):

low = 0

high = length of arr - 1

while low <= high do:

mid = (low + high) // 2

if arr[mid] == target:

return mid // Target found, return index

else if arr[mid] < target:

low = mid + 1 // Search in the right half

else:

high = mid - 1 // Search in the left half

 return -1 // Target not found

Pseudocode for Binary Search (Recursive)

BinarySearch(arr, low, high, target):

if low > high:

return -1 // Target not found

mid = (low + high) // 2

if arr[mid] == target:

return mid // Target found, return index

else if arr[mid] < target:

return BinarySearch(arr, mid + 1, high, target) // Search in the right

half

else:

return BinarySearch(arr, low, mid - 1, target) // Search in the left half

Difference Between Linear and Binary Search

The following tabular comparison present the overview of what is the

difference between linear search and binary search:

Feature Linear Search Binary Search

Time Complexity O(n) O(log n)

Best Case Time O(1) O(1)

Complexity

Worst Case Time O(n) O(log n)

Complexity

Space Complexity O(1) O(1) (Iterative) or O(log

 n) (Recursive)

Data Requirement Works on unsorted and Requires sorted list

sorted lists

Implementation Simple and easy to More complex to

Complexity implement implement

Use Case Small or unsorted Large, sorted datasets

datasets

Performance on Inefficient Highly efficient

Large Data

Applicability Can be used on any list Only on sorted lists

Pre-processing None Sorting the data before

Required searching