Quick Sort is an in-place [sorting algorithm](/tag/sorting) that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve and doesn't uses auxiliary data structures.

Quick Sort starts by selecting an element from the list to be the **pivot**, usually is the first or last element.

Next, rearrange the other elements, so all elements smaller than the pivot go to its left and all elements greater than the pivot goes to its right.

This process is repeated for the right and left sides of the pivot.

![quicksort](https://res.cloudinary.com/dje4crtui/image/upload/v1628888249/algorithms/sorting/quicksort_nag90i.gif)

## Implementation

Here is a recursive implementation of Quick Sort in [TypeScript](/tag/typescript)

```typescript
/**
 * swap function
 */
export function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

/**
 * recursive function
 */
function quickSort(arr: number[], start: number, end: number) {
  // base case
  if (start >= end) return;

  // rearrange the entire array based on a pivot
  // this pointer is the middle of the array, it will be explained in the next function
  const pointer = rearrange(arr, start, end);

  // rearrange the left and right side of the pivot
  quickSort(arr, start, pointer - 1);
  quickSort(arr, pointer + 1, end);
}

/**
 * function to rearrange the array based on a pivot
 */
function rearrange(arr: number[], start: number, end: number) {
  // choose last element to be the pivot
  const pivot = arr[end];

  // this pointer works like a placeholder for the pivot, at the end, it will be in the middle of the array, and will swap with the pivot that is in the end
  let pointer = start;

  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      swap(arr, pointer, i);

      // increment pointer, so it stays ahead of the elements that are smaller than the pivot
      pointer++;
    }
  }

  // put the pivot in the middle
  swap(arr, pointer, end);
  return pointer;
}

const arr = [3, 7, 2, 6, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // 2, 3, 5, 6, 7
```

The important part of Quick Sort is the choice of the **pivot**, since a bad choice leads to the worst-case time complexity, speaking of which, the average case time complexity of this algorithm is _O(n log n)_, while in the worst case is _O(n²)_, however, the worst-case can be avoided using a randomized version of this algorithm. Also, unlike [Merge Sort](/merge-sort), Quick Sort is an in-place algorithm, which gives it the advantage of having a constant space complexity _O(1)_.


Quick Sort is an in-place sorting algorithm that uses a divide-and-conquer technique to sort a given list

Quick Sort

Merge sort is a sorting algorithm that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve.

Merge Sort starts by splitting the list into halves, and continues to split those sublists until only sublists with a single element are left. Then merge those sublists into sorted sublists, and continue doing so until end up with a single sorted list.

```
                [4, 3, 2, 1];
                |           |
               |             |
Divide      [4,3]           [2,1]
            |   |           |   |
           |     |         |     |
         [4]     [2]     [2]     [1]
           |     |         |     |
            |   |           |   |
Conquer     [2,4]           [1,2]
                |           |
                 |         |
                 [1, 2, 3, 4]
```

## Implementation

This algorithm can be implemented with two functions, one to **divide** and another to **merge** :

```typescript
/**
 * Function to merge
 **/
function merge(left: number[], right: number[]): number[] {
  const sorted = [];

  // until one of the sublists has a element, insert them into the sorted list
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      sorted.push(left.shift());
    } else {
      sorted.push(right.shift());
    }
  }

  // one of the sublists can still have leftover elements, so we need to merge them
  return [...sorted, ...left, ...right];
}

/**
 * Function to divide
 **/
function mergeSort(list: number[]): number[] {
  // base case
  if (list.length <= 1) return list;

  // split the list into two halves
  let left = list.slice(0, list.length / 2);
  let right = list.slice(list.length / 2, list.length);

  left = mergeSort(left);
  right = mergeSort(right);

  // merge the sublists
  return merge(left, right);
}

const unsorted = [5, 4, 3, 2, 1];
const sorted = mergeSort(unsorted);
console.log(sorted); // [1, 2, 3, 4, 5]
```

Merge Sort performs in O(n log n) in terms of time complexity, its space complexity is O(n) since it uses auxiliary arrays to store the sublists.
Also, we can leverage multi-threading to implement Merge Sort, sorting each half in separated threads, for example. Moreover, we can combine Merge Sort with other [sorting algorithms](https://ricardoborges.dev/starting-with-sorting-algorithms), for example, instead of splitting the list into single element sublists, we could split into small sublists with a few elements, and apply [Insertion Sort](https://ricardoborges.dev/starting-with-sorting-algorithms) to sort them.


Merge sort is a sorting algorithm that uses a divide-and-conquer technique to sort a given list

Merge Sort

a sorting algorithm is an algorithm that sorts elements in a list into an order, among other uses, sorting can be applied to prepare a set of data for another algorithm, for example, Binary Search.

In this post, I'll describe three sorting algorithms that, although not the most efficient, are easy to understand and are in-place algorithms, meaning that they don't require auxiliary data structures.

### Bubble Sort

Bubble sort starts at the beginning of the list, comparing each pair of adjacent elements, if the first is greater than the second, it swaps them. Then it starts again at the beginning of the list and repeats this process until no swap occurred on the last pass.

![bubble sort](https://res.cloudinary.com/dje4crtui/image/upload/v1627934933/algorithms/sorting/bubble-sort_az17q6.gif)

```typescript
function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

function bubbleSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;

    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }

    if (!swapped) break;
  }
}

const arr = [5, 3, 1, 2, 4];
bubbleSort(arr);
console.log(arr);
```

Since its time complexity is Ο(n^2) on average and worst cases, this algorithm is more suitable for small or nearly ordered data sets.

### Selection Sort

The list is divided into a sorted part at the left and an unsorted part at the right in this algorithm. Initially, the sorted sublist is empty and the unsorted one is all the list. Then it searches for the smallest element in the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right.

![selection sort](https://res.cloudinary.com/dje4crtui/image/upload/v1627934933/algorithms/sorting/selection-sort_limbbw.gif)

```typescript
function selectionSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }

    swap(arr, min, i);
  }
}
```

Like Bubble Sort, this algorithm has a quadratic time complexity Ο(n^2), so it is also more suitable for small or nearly ordered data sets. However, Selection Sort performs fewer swaps than Bubble Sort.

### Insertion Sort

Insertion Sort keeps a sorted sublist at the beginning of the list, and for each element from the list, it searches for the right position in that sublist to _insert_ that element.

![insertion sort](https://res.cloudinary.com/dje4crtui/image/upload/v1627934933/algorithms/sorting/Insertion-sort_txmv8m.gif)

```typescript
function insertionSort(arr: number[]) {
  for (let i = 1; i < arr.length; i++) {
    let value = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > value) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = value;
  }
}
```

Insertion sort has a quadratic time complexity for average and worst cases too, however, it's the fastest sorting algorithm for small lists.


In this post, I'll describe three sorting algorithms that, although not the most efficient, are easy to understand.

Starting with sorting algorithms

Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B. For example, let's say there is a set of projects and some of them depend on other projects:

![graph](https://res.cloudinary.com/dje4crtui/image/upload/v1625769510/data%20structures/top_sort_q7iaub.png)

In this example project B and C depends on project A, and project D depends on projects B and C. Therefore, project A must be executed first, then projects B and C, and finally project D. Resulting in this order: [A, B, C, D] or [A, C, B, D].

Note that we start from node A because it doesn't have dependencies and repeat it, that is after A is done, B and C haven't dependencies anymore, so we can choose either one to be the next. That's why this algorithm works only on acyclic graphs.

We can use a modified depth-first search for this algorithm, [here I talk more about DPS](https://ricardoborges.dev/data-structures-in-typescript-graph). The steps are the following:

1 - For every unvisited node visit it and its adjacent nodes (DPS)
2 - After visiting a node and its adjacent add it at the beginning of a list (you can use a stack instead), this list will be in the topological order.

Here's an implementation in TypeScript, I'm using [this implementation of a graph](https://ricardoborges.dev/data-structures-in-typescript-graph):

```typescript
function topSort(
  node: Node<number>,
  visited: Map<number, boolean>,
  order: number[]
) {
  if (!node) return;

  // set node as visited
  visited.set(node.data, true);

  // for each of node's unvisited adjacent call topSort
  node.adjacent.forEach((item) => {
    if (!visited.has(item.data)) {
      topSort(item, visited, order);
    }
  });

  // add node at the beginning of the order list
  order.unshift(node.data);
}

// topological order list
const order = [];
// map to keep track of visited nodes
const visited = new Map();

// For every unvisited node visit it and its adjacent nodes
for (const entry of graph.nodes.entries()) {
  const node = entry[1];
  if (!visited.has(node.data)) {
    topSort(node, visited, order);
  }
}
```

There are other problems that topological sorting can resolve, like the order that courses have to be selected during college, since they may have other courses as a prerequisite. Or even the order of steps of a recipe, in which some must be taken before others.

There are a lot of explanations for this algorithm on the internet, here I tried to explain it in a little different way, I hope this helped you to make sense of it or if you haven't heard about topological sorting before, at least this may be an introduction of it.


Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B.