## Bubble Sort

- Runtime: O(n^2)
- Memory: O(1)

- Start at the beginning
- Swap the first 2 elements if the first > second
- Repeat until the list is sorted

```
const bubbleSort = array => {
for (i = 0; i < array.length; i++) {
for (j = 1; j < array.length; j++) {
if (array[j - 1] > array[j]) {
const temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
return array;
};
```

## Selection Sort

- Runtime: O(n^2)
- Memory: O(1)

- Find the smallest element using linear scan
- Swap the element with the first element
- Find the next smallest and swap and so on

```
const selectionSort = array => {
for (i = 0; i < array.length; i++) {
let min = i;
for (j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
if (i !== min) {
const temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
return array;
};
```

## Merge Sort

- Runtime: O(n log(n))
- Memory: O(n)

- Divide the array in half
- Sort each of the halves
- Merge back together

- Essentially it comes to sorting 2 elements at a time then merging them

```
const mergeSort = (array) => {
if (array.length == 1) {
return array;
}
const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
};
const merge = (left, right) => {
let result = [];
let indexLeft = 0;
let indexRight = 0;
while (indexLeft < left.length && indexRight < right.length) {
if (left[indexLeft] < right[indexRight]) {
result.push(left[indexLeft]);
indexLeft++;
} else {
result.push(right[indexRight]);
indexRight++;
}
}
return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight));
};
```

## Quick Sort

- Runtime: O(n log(n))
- Worst: O(n^2)
- The selected element could always be the furthest from being the median, thus it can take longer

- Memory: O(log(n))

- Pick a random element
- Partition the array with that element
- Partition all elements less than the selected element to the left and the other to the right
- Array will eventually become sorted

```
const quickSort = array => {
if (array.length <= 1) {
return array;
}
let left = [];
let right = [];
let pivot = array.pop();
for (i = 0; i < array.length; i++) {
if (array[i] <= pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return [].concat(quickSort(left), pivot, quickSort(right));
};
```

## Radix Sort

- Runtime: O(kn)

- Iterate through each digit of the number
- Group numbers by each digit
- Repeat sorting by each subsequent digit until it’s sorted