In Place Sorting

In-place sorting refers to sorting algorithms that reorder elements within the array itself, rather than copying to a new array. This is done by swapping elements systematically until sorted.

Java example (insertion sort):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    int temp = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j+1] = arr[j]; 
      j--;
    }
    arr[j+1] = temp;
  }
} 

C++ example (bubble sort):

1
2
3
4
5
6
7
8
9
void bubbleSort(vector<int>& arr) {
  for (int i = 0; i < arr.size(); i++) {
    for (int j = 0; j < arr.size() - 1; j++) {
      if (arr[j] > arr[j+1]) {
        swap(arr[j], arr[j+1]);
      }
    }
  }
}

Python example (selection sort):

1
2
3
4
5
6
7
8
def selection_sort(arr):
  for i in range(len(arr)):
    min_idx = i
    for j in range(i+1, len(arr)):
      if arr[min_idx] > arr[j]:
        min_idx = j

    arr[i], arr[min_idx] = arr[min_idx], arr[i]

In-place sorting has O(1) space complexity. Useful when extra memory allocation is undesired.