SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures

Summary: Introduces a SIMD- and cache-friendly vectorized multiway mergesort for sorting an array of structures, avoiding costly random rearrangements. Outperforms key-index SIMD and radix sort for large records, delivering up to 2.1x single-thread speedup on 512M 16-byte records and better multi-core scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11006
Venue: VLDB
Year: 2015
Pagerank: 6.0221672e-05
Overall Rank: 4,655 | 67.62%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Hiroshi Inoue
2. Kenjiro Taura

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,151	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	7.4720668e-05
4,097	The Case for a Learned Sorting Algorithm	2020	SIGMOD	6.4551616e-05
6,114	Database Processing-in-Memory: An Experimental Study	2020	VLDB	5.204248e-05
7,097	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	4.8336115e-05
7,155	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	4.8149812e-05
8,381	Interleaved Multi-Vectorizing	2020	VLDB	4.5310603e-05
9,838	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	4.2740344e-05
11,381	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
239	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00031617428
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026768139
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
930	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015238545
946	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001513324
1,607	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011162682
1,760	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	0.00010651836
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
3,655	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	6.8718304e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,832	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1945683e-05
1,760	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	0.00010651836
2,742	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1906104e-05
958	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015045316
4,832	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8924168e-05
11,381	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.1945683e-05
3,151	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	7.4720668e-05
1,607	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011162682
930	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015238545
946	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001513324