In-place sorting adalah properti algoritma sorting yang hanya menggunakan sejumlah kecil memori tambahan — biasanya O(1) — selain memori untuk input itu sendiri. Properti ini penting pada lingkungan dengan memori terbatas (embedded systems, real-time systems) atau saat menangani dataset yang besar di mana alokasi buffer O(n) tidak feasible. Beberapa algoritma (bubble, insertion, heap sort) benar-benar O(1) memori tambahan, sementara algoritma lain (merge sort, counting sort) membutuhkan O(n) atau lebih. Pada Chapter ini kita akan membedah definisi in-place, mengidentifikasi algoritma mana yang in-place, dan menunjukkan trade-off antara in-place dan stabilitas. Pada akhir chapter kita akan paham kapan in-place menjadi prioritas utama.

Definisi In-Place #

Suatu algoritma sorting disebut in-place bila memori tambahan yang digunakan selain input adalah O(1) — sejumlah konstanta variabel saja, tidak bergantung pada ukuran input n.

Catatan teknis:

  • Variabel loop, indeks, flag — dihitung O(1), tidak masalah berapa pun n.
  • Call stack rekursi — dihitung sebagai memori tambahan. Quick sort memerlukan O(log n) call stack pada best case, sehingga secara teknis bukan O(1), tetapi sering diklasifikasikan “in-place” karena O(log n) sangat kecil.
  • Buffer sementara — merge sort memerlukan O(n) buffer, sehingga tidak in-place.

Algoritma Mana yang In-Place #

In-Place (O(1) auxiliary)Tidak In-Place
Bubble sortMerge sort (O(n) buffer)
Selection sortCounting sort (O(n + k))
Insertion sortRadix sort (O(n + b))
Quick sort (O(log n) call stack)Bucket sort (O(n + k))
Heap sortTim sort (O(n) buffer)
Shell sort

Demonstrasi: In-Place vs Non In-Place #

Mari kita bandingkan insertion sort (in-place) dengan merge sort (membutuhkan buffer).

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

void insertion_sort_inplace(std::vector<int>& v) {
    for (std::size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        std::size_t j = i;
        while (j > 0 && v[j - 1] > key) {
            v[j] = v[j - 1];
            --j;
        }
        v[j] = key;
    }
}

void merge_with_buffer(std::vector<int>& v, int lo, int mid, int hi, std::vector<int>& buf) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (v[i] <= v[j]) buf[k++] = v[i++];
        else buf[k++] = v[j++];
    }
    while (i <= mid) buf[k++] = v[i++];
    while (j <= hi)  buf[k++] = v[j++];
    for (int t = lo; t <= hi; ++t) v[t] = buf[t];
}

void merge_sort(std::vector<int>& v, int lo, int hi, std::vector<int>& buf) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(v, lo, mid, buf);
    merge_sort(v, mid + 1, hi, buf);
    merge_with_buffer(v, lo, mid, hi, buf);
}

void merge_sort_non_inplace(std::vector<int>& v) {
    if (v.size() < 2) return;
    std::vector<int> buf(v.size());
    merge_sort(v, 0, static_cast<int>(v.size()) - 1, buf);
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {38, 27, 43, 3, 9, 82, 10};
    std::cout << "Sebelum      : "; print(a);

    auto b = a;
    insertion_sort_inplace(b);
    std::cout << "Insertion    : "; print(b);

    auto c = a;
    merge_sort_non_inplace(c);
    std::cout << "Merge (buf)  : "; print(c);

    auto d = a;
    std::sort(d.begin(), d.end());
    std::cout << "std::sort    : "; print(d);

    return 0;
}

Output yang Dihasilkan:

text 
Sebelum      :  38 27 43 3 9 82 10
Insertion    :  3 9 10 27 38 43 82
Merge (buf)  :  3 9 10 27 38 43 82
std::sort    :  3 9 10 27 38 43 82

Bedah Kode Baris-per-Baris #

  1. insertion_sort_inplace: hanya menggunakan variabel key, i, j — total O(1) memori tambahan. Elemen digeser di tempat tanpa buffer eksternal.
  2. merge_sort_non_inplace: mengalokasikan std::vector<int> buf(v.size()) di awal — O(n) memori tambahan. Buffer ini diperlukan karena operasi merge perlu tempat untuk menampung hasil sementara sebelum disalin kembali ke v.
  3. std::sort: mengimplementasikan introsort — in-place O(1) memori tambahan (selain call stack O(log n)).
  4. Output ketiganya identik — perbedaan hanya pada penggunaan memori, bukan hasil.

Mengapa Merge Sort Tidak In-Place #

Operasi merge pada merge sort membutuhkan dua stream input (kiri dan kanan) dan satu stream output. Tanpa buffer tambahan, hasil merge akan menimpa subarray kiri yang belum selesai diproses — korupsi data.

Beberapa varian in-place merge sort ada (misalnya block merge sort atau Katajainen), tetapi:

  • Kompleksitas konstanta jauh lebih besar (~2-3× lebih lambat).
  • Implementasi sangat kompleks — mudah bug.
  • Jarang dipakai di praktik.

Mengapa Counting/Radix/Bucket Sort Tidak In-Place #

  • Counting sort: array count berukuran k dan array output berukuran n — total O(n + k) memori tambahan. Operasi rekonstruksi membutuhkan output array terpisah karena elemen input ditimpa selama proses.
  • Radix sort: setiap pass menggunakan counting sort → O(n + b) memori tambahan per pass.
  • Bucket sort: array buckets berisi total n elemen tersebar — O(n + k) memori tambahan.

Trade-off: In-Place vs Stabilitas #

Tabel berikut menunjukkan trade-off antara in-place, stabilitas, dan kompleksitas:

AlgoritmaIn-PlaceStabilWorst Time
Bubble sortYaYaO(n²)
Insertion sortYaYaO(n²)
Selection sortYaTidakO(n²)
Merge sortTidakYaO(n log n)
Quick sortYa (O(log n))TidakO(n²) (avg O(n log n))
Heap sortYaTidakO(n log n)

Memori di Lingkungan Terbatas #

Pada lingkungan dengan memori terbatas (embedded, IoT, real-time):

  • Heap sort menjadi pilihan utama — O(1) memori, O(n log n) worst case.
  • Quick sort dengan pivot random — O(log n) call stack, namun O(n²) worst case.
  • Insertion sort untuk n kecil — O(1) memori, tetapi O(n²) time.

Mitigasi Call Stack pada Quick Sort #

Quick sort standar menggunakan rekursi sehingga call stack O(log n) best case, O(n) worst case. Untuk memori terbatas:

  1. Tail call optimization — rekursi cabang yang lebih kecil lebih dulu, cabang besar di-tail-call. Stack depth dijamin O(log n).
  2. Iteratif dengan stack eksplisit — ganti rekursi dengan loop dan stack buatan sendiri. Stack dapat di-batasi ukurannya.
  3. Introsort — switch ke heap sort bila kedalaman melebihi 2·log₂ n.

Pengukuran Memori: Praktik #

Pada n = 1.000.000 elemen int (4 byte):

  • Input: 4 MB (tidak terhindarkan).
  • Heap sort: + beberapa byte (variabel lokal).
  • Quick sort: + ~120 byte (call stack 2·log₂ n ≈ 40 frame).
  • Merge sort: + 4 MB (buffer duplikat).
  • Counting sort: + 4 MB + k byte (output + count).

Bila dataset berukuran n = 100 juta:

  • Heap sort tetap berjalan dengan memori tambahan ~1 KB.
  • Merge sort memerlukan 400 MB tambahan — mungkin tidak feasible.

Aplikasi In-Place Sorting #

  • Embedded systems — memori terbatas, tidak boleh alokasi dinamis berlebihan.
  • Real-time systems — alokasi dinamis dapat menyebabkan fragmentation dan pelanggaran deadline.
  • Database buffer sort — mengurutkan page di tempat untuk efisiensi I/O.
  • Kernel mode — alokasi dinamis terbatas, prefer in-place.

Variasi In-Place dengan Kompromi #

  1. In-place merge sort (block merge sort) — O(1) memori, stabil, O(n log n) worst case. Konstanta ~2-3× lebih lambat dari merge sort standar. Implementasi sangat kompleks.
  2. Quick sort dengan insertion cutoff — quick sort hingga sub-array ≤ 16, lalu insertion sort. Mengurangi call stack dan memanfaatkan adaptifitas insertion sort.
  3. Smooth sort — varian heap sort adaptif, O(n) pada data hampir terurut, O(n log n) worst case, O(1) memori. Tidak stabil, konstanta besar.

Ringkasan #

  • In-place = O(1) memori tambahan (atau O(log n) untuk rekursi).
  • In-place: bubble, selection, insertion, quick, heap, shell sort.
  • Tidak in-place: merge, counting, radix, bucket, Tim sort.
  • Trade-off klasik: tidak ada algoritma comparison-based yang in-place + stabil + O(n log n) worst case sekaligus (kecuali block merge sort dengan konstanta besar).
  • Heap sort menjadi pilihan utama untuk memori sangat terbatas.
  • std::sort (introsort) in-place dan O(n log n) worst case — pilihan default untuk kode produksi.

Pada chapter berikutnya kita akan merangkum seluruh algoritma sorting dalam tabel perbandingan komprehensif, dengan rekomendasi kapan menggunakan masing-masing.