### Quick Sort

##### Sort Algorithm:

- If left >= right the
- return

- Recursively call sort function with left to pivot – 1 index
- Recursively call sort function with pivot + 1 to right index

##### Partition Algorithm:

- Set pivot = array[end]
- Set pivot_index = start
- Iterate from start to end of
- If array[i] < pivot then
- Swap ith index data with pivot_index data
- Increase pivot_index by 1

- If array[i] < pivot then
- Swap pivot_index with end_index
- return pivot_index

Merge Sort | Quick Sort |
---|---|

Worst case O(nlogn) | Avg case O(nlogn) and, wors case O(n ^{2}) |

O(n) – space complexity (not in-place sorting) | O(n) – constant (in-place sorting) |

Source Code:

Github: QuickSort.java

**Output:**

Before sort: 7 3 18 9 1 2 15 12 5 After sort: 1 2 3 5 7 9 12 15 18