QS vs Dual Pivot QS

Benchmark created on

Setup

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;

  for (let j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}


// ========== //



function swap(arr,i,j) 
{ 
	let temp = arr[i]; 
	arr[i] = arr[j]; 
	arr[j] = temp; 
} 
	
function dualPivotQuickSort(arr,low,high) 
{ 
	if (low < high) 
	{ 
		
		// piv[] stores left pivot and right pivot. 
		// piv[0] means left pivot and 
		// piv[1] means right pivot 
		let piv = []; 
    piv = partitionDualPivot(arr, low, high); 
		
		dualPivotQuickSort(arr, low, piv[0] - 1); 
		dualPivotQuickSort(arr, piv[0] + 1, piv[1] - 1); 
		dualPivotQuickSort(arr, piv[1] + 1, high); 
	} 
} 
	
function partitionDualPivot(arr,low,high) 
{ 
	if (arr[low] > arr[high]) 
		swap(arr, low, high); 

	let j = low + 1; 
	let g = high - 1, k = low + 1, 
		p = arr[low], q = arr[high]; 
		
	while (k <= g) 
	{ 
		if (arr[k] < p) 
		{ 
			swap(arr, k, j); 
			j++; 
		} 
		else if (arr[k] >= q) 
		{ 
			while (arr[g] > q && k < g) 
				g--; 
				
			swap(arr, k, g); 
			g--; 
			
			if (arr[k] < p) 
			{ 
				swap(arr, k, j); 
				j++; 
			} 
		} 
		k++; 
	} 
	j--; 
	g++; 
		
	swap(arr, low, j); 
	swap(arr, high, g); 
	return [ j, g ]; 
}

Test runner

Ready to run.

Testing in
TestOps/sec
QS
const arr = [4442, 5448, 7958, 9166, 1122, 6689, 6377, 3705, 8390, 8158, 2465, 4501, 6111, 6244, 8036, 6658, 9637, 4911, 4980, 4534, 6958, 7197, 4793, 3732, 4013, 5386, 5306, 558, 8932, 674, 2146, 6693, 4762, 1047, 8030, 1658, 4504, 4286, 2085, 2464, 153, 6974, 692, 1493, 1390, 8955, 5200, 9406, 5804, 6383, 1602, 9253, 3573, 3701, 2249, 9756, 1699, 4311, 2916, 5325, 7512, 2669, 1996, 822, 3490, 385, 7310, 9655, 5782, 9175, 9339, 5032, 9059, 1912, 9451, 6864, 927, 9956, 3028, 197, 5094, 8051, 3607, 4192, 9341, 7006, 5400, 1472, 5716, 4721, 2535, 3295, 7531, 9815, 1349, 6242, 3438, 740, 2896, 2758, 2828, 4570, 2668, 1723, 6717, 6480, 5678, 7800, 414, 1576, 626, 6337, 5369, 6619, 5190, 9634, 7775, 2913, 3694, 6134, 9702, 4271, 6261, 790, 3974, 2349, 2057, 6203, 8152, 1968, 1745, 1105, 9761, 8694, 1193, 6883, 7772, 5387, 7973, 3120, 1110, 7407, 6303, 1142, 4475, 8040, 5402, 36, 5927, 5677, 9446, 7578, 1448, 9704, 1484, 8770, 7021, 9192, 2168, 6210, 5766, 8681, 6283, 3826, 6666, 770, 1717, 8963, 4742, 2270, 6208, 3511, 5800, 4680, 3809, 1606, 7128, 7824, 2660, 4181, 7715, 7379, 9968, 8897, 7267, 9515, 3845, 1236, 8521, 5745, 6700, 4036, 6778, 9269, 3876, 4849, 2762, 2773, 8889, 6118, 3196, 4909, 8740, 8288, 556, 1468, 1771, 2434, 3713, 6274, 9189, 8382, 5026, 450, 3467, 7760, 1135, 8715, 3956, 5228, 8, 8940, 7627, 9136, 6163, 5807, 9342, 4731, 6736, 4500, 411, 8308, 2430, 1972, 4643, 1285, 7141, 9805, 4425, 3789, 5164, 5275, 9065, 7480, 5447, 4989, 2940, 1037, 7518, 33, 7265, 4753, 1584, 9334, 4403, 5073, 8434, 9105, 5419, 4168, 3667, 9046, 8803, 6744, 1919, 3879, 1497, 1377, 9783, 1178, 8294, 8867, 4019, 7703, 4089, 454, 6123, 7394, 5310, 8022, 4653, 2268, 6895, 7844, 7204, 7279, 6095, 3650, 6885, 5408, 6675, 2741, 6277, 4508, 6485, 3714, 7665, 7939, 1574, 2647, 8198, 5441, 9994, 4892, 612, 2689, 5260, 7890, 1629, 309, 1391, 2859, 2656, 2462, 8729, 148, 6493, 954, 1580, 384, 1713, 5005, 6488, 5054, 8780, 9321, 5444, 1050, 8325, 8851, 4558, 1215, 442, 1920, 1725, 5219, 4497, 580, 3796, 3155, 143, 7567, 2308, 2009, 8801, 9712, 8943, 3991, 1831, 4337, 8862, 2374, 8117, 9418, 8446, 3976, 565, 5598, 2018, 132, 8699, 235, 2017, 2372, 248, 4139, 5945, 4398, 1124, 5342, 5849, 6704, 5499, 44, 2619, 4288, 9585, 4304, 6229, 1007, 7942, 1865, 8341, 5343, 7778, 9788, 3279, 7684, 1994, 4236, 7331, 9116, 601, 6529, 7696, 7431, 1156, 3488, 5834, 4696, 2191, 6667, 9040, 9029, 1385, 5733, 5114, 9933, 5643, 889, 9256, 1932, 1556, 90, 5192, 6899, 6029, 6393, 84, 6385, 7000, 6087, 5057, 749, 9404, 1207, 8423, 9308, 7306, 9632, 465, 6228, 8218, 6089, 5921, 4647, 5367, 7682, 974, 2899, 9039, 8893, 7607, 4336, 3232, 6522, 9589, 2128, 459, 1251, 1146, 2481, 1376, 6759, 7818, 8743, 2514, 9786, 2848, 7333, 278, 2139, 1945, 5520, 2832, 268, 8566, 8007, 9262, 6062, 9614, 378, 2478, 3007, 3727, 8724, 7466, 5799, 5505, 5623, 9891, 7609, 7424, 4320, 1915, 3795, 651, 2391, 2526, 3169, 8148, 753, 8806, 8935, 2909, 5351, 3949, 7777, 6782, 4725, 9471, 7018, 8907, 7711, 8174, 7302, 4362, 7125, 8714, 7786, 9875, 6188, 6957, 8243, 9850, 6768, 6709, 5596, 3798, 4846, 3485, 9742, 9162, 5938, 842, 4535, 819, 6414, 3244, 3072, 9706, 8580, 1176, 2506, 64, 1953, 5254, 45, 2823, 190, 1470, 807, 3716, 6948, 5824, 7797, 7497, 9910, 5535, 5585, 368, 5791, 9937, 7754, 4994, 4738, 7, 9865, 6270, 8116, 1120, 8104, 4370, 2060, 8628, 1729, 4171, 9923, 7181, 8227, 8651, 7592, 4383, 7562, 4772, 7221, 6156, 4006, 5465, 1661, 508, 1096, 4732, 4114, 7694, 905, 808, 7126, 7537, 7428, 9559, 3676, 9221, 8496, 7646, 3469, 9774, 860, 9525, 5768, 657, 9384, 1262, 1381, 8246, 8079, 1457, 5587, 9050, 2239, 6342, 5201, 4673, 8872, 9520, 3602, 1005, 1337, 4470, 813, 2259, 932, 9048, 4495, 7792, 9126, 2508, 800, 7217, 5933, 7493, 5798, 3406, 9194, 1197, 195, 6434, 3567, 6635, 5653, 8587, 6402, 4071, 280, 3392, 3226, 3744, 8947, 9997, 2295, 3852, 8953, 2900, 4328, 9419, 4017, 321, 7934, 1214, 2277, 6549, 3001, 2172, 8039, 1966, 2568, 6068, 4795, 1181, 277, 9323, 4985, 9574, 1439, 1626, 9057, 4719, 7988, 4243, 9432, 7565, 2527, 4744, 8175, 7914, 9541, 9975, 5439, 3108, 4290, 6906, 9555, 1894, 8396, 1543, 2442, 9386, 9847, 3225, 8868, 3632, 2674, 9660, 7365, 3445, 3356, 4244, 5723, 5987, 9178, 9023, 4275, 4426, 804, 8787, 9121, 7989, 9379, 4070, 8702, 2064, 1683, 5922, 8013, 1192, 3391, 8939, 4819, 2136, 5169, 543, 5120, 9096, 294, 7391, 5631, 4806, 684, 2204, 9971, 5072, 9713, 2245, 2330, 7422, 4283, 3742, 4486, 8205, 8352, 9864, 3248, 569, 653, 8980, 4433, 9157, 4458, 3199, 8149, 2657, 4313, 2388, 5790, 6030, 6777, 5251, 23, 6141, 2885, 9377, 3805, 6894, 5280, 907, 5864, 3739, 2400, 3124, 5749, 4518, 9373, 2635, 5603, 6201, 6171, 6145, 3350, 3508, 4872, 7232, 4094, 4389, 7766, 2093, 2509, 8833, 276, 6910, 663, 3859, 6741, 2749, 2015, 9548, 6169, 3234, 1820, 9715, 2781, 7739, 2768, 7807, 6078, 5423, 5979, 8273, 7548, 6483, 8464, 7668, 5038, 1295, 4955, 998, 4726, 8820, 1383, 2426, 1787, 2148, 920, 571, 117, 6082, 1551, 9112, 1644, 2042, 8003, 1139, 1186, 7271, 7911, 5239, 2332, 7757, 584, 1684, 8311, 2309, 4856, 7260, 8283, 4735, 4986, 2956, 4883, 405, 4082, 9567, 2088, 7608, 1675, 485, 779, 5495, 365, 225, 1890, 2888, 9623, 1092, 9411, 1389, 7322, 3950, 1309, 5039, 6394, 9626, 9569, 4237, 1882, 1636, 8417, 114, 2917, 5450, 5279, 452, 282, 7059, 8176, 1461, 9973, 2252, 4005, 1722, 5786, 2963, 4247, 2278, 7462, 491, 8637, 9689, 3636, 1495, 6821, 4604, 5682, 3324, 3054, 780, 5549, 320, 3163, 5414, 8188, 6259, 5713, 9395, 705, 9877, 1025, 7452, 9943, 7851, 6129, 4766, 6317, 6288, 8163, 9368, 4473, 7850, 1982, 7695, 5874, 2820, 3614, 311, 6295, 9741, 8908, 706, 1443, 7341, 7789, 3146, 1333, 9257, 2166, 4402, 6727, 7293, 3623, 3620, 4331, 2826, 2757, 5095, 6692, 6273, 7950, 2133, 3283, 2174, 4041, 9722, 7429, 7870, 3242, 2992, 3886, 7559, 643, 4818, 2986, 4250, 6389, 586, 6933, 7058, 2116, 7233, 2892, 2833, 8805, 7443, 9857, 5940, 4056, 1049, 2764, 9211, 9118, 7489, 2284]
const l = arr.length - 1

quickSort(arr, 0, l);
ready
Dual Pivot QS
const arr = [4442, 5448, 7958, 9166, 1122, 6689, 6377, 3705, 8390, 8158, 2465, 4501, 6111, 6244, 8036, 6658, 9637, 4911, 4980, 4534, 6958, 7197, 4793, 3732, 4013, 5386, 5306, 558, 8932, 674, 2146, 6693, 4762, 1047, 8030, 1658, 4504, 4286, 2085, 2464, 153, 6974, 692, 1493, 1390, 8955, 5200, 9406, 5804, 6383, 1602, 9253, 3573, 3701, 2249, 9756, 1699, 4311, 2916, 5325, 7512, 2669, 1996, 822, 3490, 385, 7310, 9655, 5782, 9175, 9339, 5032, 9059, 1912, 9451, 6864, 927, 9956, 3028, 197, 5094, 8051, 3607, 4192, 9341, 7006, 5400, 1472, 5716, 4721, 2535, 3295, 7531, 9815, 1349, 6242, 3438, 740, 2896, 2758, 2828, 4570, 2668, 1723, 6717, 6480, 5678, 7800, 414, 1576, 626, 6337, 5369, 6619, 5190, 9634, 7775, 2913, 3694, 6134, 9702, 4271, 6261, 790, 3974, 2349, 2057, 6203, 8152, 1968, 1745, 1105, 9761, 8694, 1193, 6883, 7772, 5387, 7973, 3120, 1110, 7407, 6303, 1142, 4475, 8040, 5402, 36, 5927, 5677, 9446, 7578, 1448, 9704, 1484, 8770, 7021, 9192, 2168, 6210, 5766, 8681, 6283, 3826, 6666, 770, 1717, 8963, 4742, 2270, 6208, 3511, 5800, 4680, 3809, 1606, 7128, 7824, 2660, 4181, 7715, 7379, 9968, 8897, 7267, 9515, 3845, 1236, 8521, 5745, 6700, 4036, 6778, 9269, 3876, 4849, 2762, 2773, 8889, 6118, 3196, 4909, 8740, 8288, 556, 1468, 1771, 2434, 3713, 6274, 9189, 8382, 5026, 450, 3467, 7760, 1135, 8715, 3956, 5228, 8, 8940, 7627, 9136, 6163, 5807, 9342, 4731, 6736, 4500, 411, 8308, 2430, 1972, 4643, 1285, 7141, 9805, 4425, 3789, 5164, 5275, 9065, 7480, 5447, 4989, 2940, 1037, 7518, 33, 7265, 4753, 1584, 9334, 4403, 5073, 8434, 9105, 5419, 4168, 3667, 9046, 8803, 6744, 1919, 3879, 1497, 1377, 9783, 1178, 8294, 8867, 4019, 7703, 4089, 454, 6123, 7394, 5310, 8022, 4653, 2268, 6895, 7844, 7204, 7279, 6095, 3650, 6885, 5408, 6675, 2741, 6277, 4508, 6485, 3714, 7665, 7939, 1574, 2647, 8198, 5441, 9994, 4892, 612, 2689, 5260, 7890, 1629, 309, 1391, 2859, 2656, 2462, 8729, 148, 6493, 954, 1580, 384, 1713, 5005, 6488, 5054, 8780, 9321, 5444, 1050, 8325, 8851, 4558, 1215, 442, 1920, 1725, 5219, 4497, 580, 3796, 3155, 143, 7567, 2308, 2009, 8801, 9712, 8943, 3991, 1831, 4337, 8862, 2374, 8117, 9418, 8446, 3976, 565, 5598, 2018, 132, 8699, 235, 2017, 2372, 248, 4139, 5945, 4398, 1124, 5342, 5849, 6704, 5499, 44, 2619, 4288, 9585, 4304, 6229, 1007, 7942, 1865, 8341, 5343, 7778, 9788, 3279, 7684, 1994, 4236, 7331, 9116, 601, 6529, 7696, 7431, 1156, 3488, 5834, 4696, 2191, 6667, 9040, 9029, 1385, 5733, 5114, 9933, 5643, 889, 9256, 1932, 1556, 90, 5192, 6899, 6029, 6393, 84, 6385, 7000, 6087, 5057, 749, 9404, 1207, 8423, 9308, 7306, 9632, 465, 6228, 8218, 6089, 5921, 4647, 5367, 7682, 974, 2899, 9039, 8893, 7607, 4336, 3232, 6522, 9589, 2128, 459, 1251, 1146, 2481, 1376, 6759, 7818, 8743, 2514, 9786, 2848, 7333, 278, 2139, 1945, 5520, 2832, 268, 8566, 8007, 9262, 6062, 9614, 378, 2478, 3007, 3727, 8724, 7466, 5799, 5505, 5623, 9891, 7609, 7424, 4320, 1915, 3795, 651, 2391, 2526, 3169, 8148, 753, 8806, 8935, 2909, 5351, 3949, 7777, 6782, 4725, 9471, 7018, 8907, 7711, 8174, 7302, 4362, 7125, 8714, 7786, 9875, 6188, 6957, 8243, 9850, 6768, 6709, 5596, 3798, 4846, 3485, 9742, 9162, 5938, 842, 4535, 819, 6414, 3244, 3072, 9706, 8580, 1176, 2506, 64, 1953, 5254, 45, 2823, 190, 1470, 807, 3716, 6948, 5824, 7797, 7497, 9910, 5535, 5585, 368, 5791, 9937, 7754, 4994, 4738, 7, 9865, 6270, 8116, 1120, 8104, 4370, 2060, 8628, 1729, 4171, 9923, 7181, 8227, 8651, 7592, 4383, 7562, 4772, 7221, 6156, 4006, 5465, 1661, 508, 1096, 4732, 4114, 7694, 905, 808, 7126, 7537, 7428, 9559, 3676, 9221, 8496, 7646, 3469, 9774, 860, 9525, 5768, 657, 9384, 1262, 1381, 8246, 8079, 1457, 5587, 9050, 2239, 6342, 5201, 4673, 8872, 9520, 3602, 1005, 1337, 4470, 813, 2259, 932, 9048, 4495, 7792, 9126, 2508, 800, 7217, 5933, 7493, 5798, 3406, 9194, 1197, 195, 6434, 3567, 6635, 5653, 8587, 6402, 4071, 280, 3392, 3226, 3744, 8947, 9997, 2295, 3852, 8953, 2900, 4328, 9419, 4017, 321, 7934, 1214, 2277, 6549, 3001, 2172, 8039, 1966, 2568, 6068, 4795, 1181, 277, 9323, 4985, 9574, 1439, 1626, 9057, 4719, 7988, 4243, 9432, 7565, 2527, 4744, 8175, 7914, 9541, 9975, 5439, 3108, 4290, 6906, 9555, 1894, 8396, 1543, 2442, 9386, 9847, 3225, 8868, 3632, 2674, 9660, 7365, 3445, 3356, 4244, 5723, 5987, 9178, 9023, 4275, 4426, 804, 8787, 9121, 7989, 9379, 4070, 8702, 2064, 1683, 5922, 8013, 1192, 3391, 8939, 4819, 2136, 5169, 543, 5120, 9096, 294, 7391, 5631, 4806, 684, 2204, 9971, 5072, 9713, 2245, 2330, 7422, 4283, 3742, 4486, 8205, 8352, 9864, 3248, 569, 653, 8980, 4433, 9157, 4458, 3199, 8149, 2657, 4313, 2388, 5790, 6030, 6777, 5251, 23, 6141, 2885, 9377, 3805, 6894, 5280, 907, 5864, 3739, 2400, 3124, 5749, 4518, 9373, 2635, 5603, 6201, 6171, 6145, 3350, 3508, 4872, 7232, 4094, 4389, 7766, 2093, 2509, 8833, 276, 6910, 663, 3859, 6741, 2749, 2015, 9548, 6169, 3234, 1820, 9715, 2781, 7739, 2768, 7807, 6078, 5423, 5979, 8273, 7548, 6483, 8464, 7668, 5038, 1295, 4955, 998, 4726, 8820, 1383, 2426, 1787, 2148, 920, 571, 117, 6082, 1551, 9112, 1644, 2042, 8003, 1139, 1186, 7271, 7911, 5239, 2332, 7757, 584, 1684, 8311, 2309, 4856, 7260, 8283, 4735, 4986, 2956, 4883, 405, 4082, 9567, 2088, 7608, 1675, 485, 779, 5495, 365, 225, 1890, 2888, 9623, 1092, 9411, 1389, 7322, 3950, 1309, 5039, 6394, 9626, 9569, 4237, 1882, 1636, 8417, 114, 2917, 5450, 5279, 452, 282, 7059, 8176, 1461, 9973, 2252, 4005, 1722, 5786, 2963, 4247, 2278, 7462, 491, 8637, 9689, 3636, 1495, 6821, 4604, 5682, 3324, 3054, 780, 5549, 320, 3163, 5414, 8188, 6259, 5713, 9395, 705, 9877, 1025, 7452, 9943, 7851, 6129, 4766, 6317, 6288, 8163, 9368, 4473, 7850, 1982, 7695, 5874, 2820, 3614, 311, 6295, 9741, 8908, 706, 1443, 7341, 7789, 3146, 1333, 9257, 2166, 4402, 6727, 7293, 3623, 3620, 4331, 2826, 2757, 5095, 6692, 6273, 7950, 2133, 3283, 2174, 4041, 9722, 7429, 7870, 3242, 2992, 3886, 7559, 643, 4818, 2986, 4250, 6389, 586, 6933, 7058, 2116, 7233, 2892, 2833, 8805, 7443, 9857, 5940, 4056, 1049, 2764, 9211, 9118, 7489, 2284]

dualPivotQuickSort(arr, 0, 7);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.