#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Merge Sort — O(n log n), stable
void merge(vector<int>& arr, int l, int mid, int r) {
vector<int> left(arr.begin()+l, arr.begin()+mid+1);
vector<int> right(arr.begin()+mid+1, arr.begin()+r+1);
int i=0, j=0, k=l;
while (i<left.size() && j<right.size())
arr[k++] = (left[i]<=right[j]) ? left[i++] : right[j++];
while (i<left.size()) arr[k++] = left[i++];
while (j<right.size()) arr[k++] = right[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int mid = l + (r-l)/2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
}
// Quick Sort — O(n log n) avg, in-place
int partition(vector<int>& arr, int lo, int hi) {
int pivot = arr[hi], i = lo-1;
for (int j=lo; j<hi; j++)
if (arr[j]<=pivot) swap(arr[++i], arr[j]);
swap(arr[i+1], arr[hi]);
return i+1;
}
void quickSort(vector<int>& arr, int lo, int hi) {
if (lo < hi) {
int pi = partition(arr, lo, hi);
quickSort(arr, lo, pi-1);
quickSort(arr, pi+1, hi);
}
}
int main() {
vector<int> a = {38,27,43,3,9,82,10};
mergeSort(a, 0, a.size()-1);
for (int x : a) cout << x << " "; // 3 9 10 27 38 43 82
cout << endl;
vector<int> b = {10,7,8,9,1,5};
quickSort(b, 0, b.size()-1);
for (int x : b) cout << x << " "; // 1 5 7 8 9 10
cout << endl;
// STL sort
vector<int> c = {5,3,1,4,2};
sort(c.begin(), c.end()); // O(n log n) — introsort
for (int x : c) cout << x << " "; // 1 2 3 4 5
return 0;
}
import java.util.Arrays;
public class SortingAlgorithms {
// Merge Sort
static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
}
static void merge(int[] arr, int l, int mid, int r) {
int[] L = Arrays.copyOfRange(arr, l, mid+1);
int[] R = Arrays.copyOfRange(arr, mid+1, r+1);
int i=0, j=0, k=l;
while (i<L.length && j<R.length) arr[k++] = L[i]<=R[j] ? L[i++] : R[j++];
while (i<L.length) arr[k++] = L[i++];
while (j<R.length) arr[k++] = R[j++];
}
// Quick Sort
static void quickSort(int[] arr, int lo, int hi) {
if (lo < hi) {
int pi = partition(arr, lo, hi);
quickSort(arr, lo, pi-1);
quickSort(arr, pi+1, hi);
}
}
static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi], i = lo-1;
for (int j=lo; j<hi; j++)
if (arr[j]<=pivot) { int t=arr[++i]; arr[i]=arr[j]; arr[j]=t; }
int t=arr[i+1]; arr[i+1]=arr[hi]; arr[hi]=t;
return i+1;
}
public static void main(String[] args) {
int[] a = {38,27,43,3,9,82,10};
mergeSort(a, 0, a.length-1);
System.out.println(Arrays.toString(a)); // [3, 9, 10, 27, 38, 43, 82]
int[] b = {10,7,8,9,1,5};
quickSort(b, 0, b.length-1);
System.out.println(Arrays.toString(b)); // [1, 5, 7, 8, 9, 10]
// Built-in sort
int[] c = {5,3,1,4,2};
Arrays.sort(c);
System.out.println(Arrays.toString(c)); // [1, 2, 3, 4, 5]
}
}
# Merge Sort — O(n log n), stable
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: result.append(left[i]); i += 1
else: result.append(right[j]); j += 1
return result + left[i:] + right[j:]
# Quick Sort — O(n log n) avg
def quick_sort(arr):
if len(arr) <= 1: return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [38, 27, 43, 3, 9, 82, 10]
print("Merge sort:", merge_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]
print("Quick sort:", quick_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]
# Built-in sort (Timsort — O(n log n), stable)
arr.sort() # in-place
sorted_arr = sorted(arr) # returns new list
# Sort with key
words = ["banana", "apple", "cherry", "date"]
words.sort(key=len) # sort by length
print(words) # ['date', 'apple', 'banana', 'cherry']
# Sort objects
students = [("Alice", 90), ("Bob", 85), ("Carol", 92)]
students.sort(key=lambda s: s[1], reverse=True)
print(students) # [('Carol', 92), ('Alice', 90), ('Bob', 85)]
// Merge Sort — O(n log n), stable
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
// Quick Sort — O(n log n) avg
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Merge sort:", mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]
console.log("Quick sort:", quickSort(arr)); // [3, 9, 10, 27, 38, 43, 82]
// Built-in sort (IMPORTANT: default sort is lexicographic!)
[3, 1, 10, 2].sort(); // [1, 10, 2, 3] — WRONG for numbers!
[3, 1, 10, 2].sort((a,b) => a-b); // [1, 2, 3, 10] — correct
// Sort objects
const students = [{name:"Alice",score:90},{name:"Bob",score:85},{name:"Carol",score:92}];
students.sort((a, b) => b.score - a.score);
console.log(students.map(s => s.name)); // ['Carol', 'Alice', 'Bob']