# QuickSort implementation in TypeScript using recursion

This post will discuss how to implement the `QuickSort` algorithm in typescript/javascript. Quicksort is the fastest algorithm. Quicksort works on the divide and conquer strategy. All languages in the world provide sorting functionality which implements `QuickSort` with some modifications.

## What is divide and conquer

As per the Wikipedia

A divide-and-conquer algorithm breaks down a problem into two or more sub-problems of the same or similar type in a recursive manner. Wikipedia

## Choosing Pivot Point

Choosing a pivot point is also very important in `QuickSort`. You can select first, last or middle as a pivot element.

Quicksort algorithm follows the following steps.

Step 1 Choose the pivot element.

Step 2 Divide the array into two pieces, one smaller than the pivot and the other larger.

Step 3 recursively sort the left half.

Step 4 recursively sort the right half.

## The complexity of QuickSort is

• Best Case `O(nlogn).`
• Worst cases `O(n^2)`.

## Implementation

``````export function QuickSort(
arr: Array<number>,
start: number = 0,
end: number = arr.length
): Array<number> {
if (start < end) {
let p = partition(arr, start, end);
QuickSort(arr, start, p - 1);
QuickSort(arr, p + 1, end);
}
return arr;
}

function partition(
arr: Array<number>,
start: number = 0,
end: number = arr.length
) {
let pivot: number = arr[start];
let swapIndex: number = start;
for (let i = start + 1; i < end; i++) {
if (arr[i] < pivot) {
swapIndex++;
swap(arr, i, swapIndex);
}
}
swap(arr, start, swapIndex);
return swapIndex;
}

function swap(arr: Array<number>, i: number, j: number) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
``````