You can see the whole Data Structure and Algorithms project on GitHub.

**Time Complexity:**

- Best Case:
**O(n)** - Avg Case:
**O(n^2)** - Worst Case:
**O(n^2)**

**Space Complexity:** **O(1)**

**Java Code: **

```
public void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// inner loop upto 2nd last element
for (int j = 0; j < arr.length - 1; j++) {
// if current element is greater than the next one, swap them
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
```

Code language: JavaScript (javascript)

**Time Complexity:**

- Best Case:
**O(n)** - Avg Case:
**O(n^2)** - Worst Case:
**O(n^2)**

**Space Complexity:** **O(1)**

**Java Code: **

```
public void sort(int[] arr) {
// start with 2nd element assuming the 0th element is sorted
for (int i = 1; i < arr.length; i++) {
// copy the current element
int curr = arr[i];
int j = i - 1; // traverse the left side excluding current
// shift element to right until
// the element is greater than the 'curr'
// or you reach the start of the array
while (j >= 0 && arr[j] > curr) {
arr[j + 1] = arr[j]; // shift the element to right
j--; // move pointer to one index left
}
// INSERT the current element resulting the left side as sorted
arr[j + 1] = curr;
}
}
```

Code language: JavaScript (javascript)

**Time Complexity:**

- Best Case:
**O(n^2)** - Avg Case:
**O(n^2)** - Worst Case:
**O(n^2)**

**Space Complexity:** **O(1)**

**Java Code: **

```
public void sort(int[] arr) {
// Select the minimum on the right side
// and swap it with the current value
for (int i = 0; i < arr.length; i++) {
int minValIndex = i;
// traverse right side of the array from curr element
for (int j = i + 1; j < arr.length; j++) {
// if the current index value is less than min value
// make current index as min value index
if (arr[j] < arr[minValIndex]) {
minValIndex = j;
}
}
// swap the current value with minValIndex value
swap(arr, i, minValIndex);
}
}
```

Code language: JavaScript (javascript)

**Time Complexity:**

- Best Case:
**O(n log n)** - Avg Case:
**O(n log n)** - Worst Case:
**O(n^2)**

**Space Complexity:** **O(n)**

**Java Code: **

**QuickSort Code:**

```
public void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public void quickSort(int[] arr, int left, int right) {
// in case it has one or zero elements don't do anything
if (left >= right) return;
// partition i.e. sort the array and get partitioned index
int partitionedIndex = partition(arr, left, right);
// repeat the process for right side
quickSort(arr, left, partitionedIndex - 1); // important to use -1
// repeat the process for left side
quickSort(arr, partitionedIndex, right);
}
```

Code language: JavaScript (javascript)

**Quick Sort Partitioning Code:**

```
private int partition(int[] arr, int left, int right) {
// it's best to use middle as pivot index
int pivotIndex = left + (right - left) / 2;
int pivotValue = arr[pivotIndex];
// sort the array from pivot such that
// left side is less than pivot and right side is greater than pivot
while (left <= right) {
// move left pointer to right until its left value is smaller
while (arr[left] < pivotValue) left++;
// move right pointer to left until its right value is greater
while (arr[right] > pivotValue) right--;
// swap the values of left and right in case
// left index is equal to or less than right index
if (left <= right) {
swap(arr, left, right);
// move the pointer to skip the processed index
left++;
right--;
}
}
// return the left index as partition Index
return left;
}
```

Code language: PHP (php)

**Time Complexity:**

- Best Case:
**O(n log n)** - Avg Case:
**O(n log n)** - Worst Case:
**O(n log n)**

**Space Complexity:** **O(n)**

**Java Code: **

**MergeSort:**

```
public void sort(int[] arr) {
int[] tempArr = new int[arr.length];
mergeSort(arr, tempArr, 0, arr.length - 1);
}
public void mergeSort(int[] arr, int[] tempArr, int left, int right) {
// in case of one or zero element do nothing
if (left >= right) return;
int mid = left + (right - left) / 2; // or (right + left) /2
// sort left side
mergeSort(arr, tempArr, left, mid);
// sort right side
mergeSort(arr, tempArr, mid + 1, right);
// merge the sorted array
mergeSortedArray(arr, tempArr, left, right);
}
```

Code language: JavaScript (javascript)

**Merge Sorted Array Code:**

```
private void mergeSortedArray(int[] arr, int[] tempArr, int left, int right) {
int leftStart = left;
int rightEnd = right;
int leftEnd = leftStart + (rightEnd - leftStart) / 2; // simply middle index
int rightStart = leftEnd + 1;
int sortedIndex = leftStart;
// traverse until one of the start index reaches corresponding end index
while (leftStart <= leftEnd && rightStart <= rightEnd) {
// if left value is smaller or equal than the right side,
// use it and increment left pointer
if (arr[leftStart] <= arr[rightStart]) {
tempArr[sortedIndex] = arr[leftStart];
leftStart++;
} else { // else use right index and increment right index
tempArr[sortedIndex] = arr[rightStart];
rightStart++;
}
sortedIndex++; // increment it anyway
}
// in case one of the array reaches the end first, we need to
// make sure remaining values are copied.
/** I used arraycopy but for simplicity you can use while loop also */
// copy left array if remaining
// (leftEnd - leftStart + 1) will give zero if nothing remaining
System.arraycopy(arr, leftStart, tempArr, sortedIndex, leftEnd - leftStart + 1);
// copy right array if remaining
// (rightEnd - rightStart + 1) will give zero if nothing remaining
System.arraycopy(arr, rightStart, tempArr, sortedIndex, rightEnd - rightStart + 1);
// copy the full temp array from left to right
System.arraycopy(tempArr, left, arr, left, right - left + 1);
}
```

Code language: PHP (php)

I have added a test in the GitHub repo so that you can play around and check if it’s working or not.

Here is the Test code Link.

I will be updating this as I write more algorithms and explanations. I will try to include a table of content as well for better navigation. Please feel free to give any feedback as I am trying to write more and more and need some motivation as well.

You can check out other posts of me in Java, Spring, or Best Practices in the programming world.

See you in the next post. HAKUNA MATATA!!!

I would be happy to connect with you guys on social media. It’s **@coderstea** on Twitter, Linkedin, Facebook, Instagram, and YouTube.

Please Subscribe to the newsletter to know about the latest posts from CodersTea.