Bulk-Insertion Sort: Towards Composite Measures of Presortedness | SpringerLink
Skip to main content
Springer Nature Link
Log in

Bulk-Insertion Sort: Towards Composite Measures of Presortedness

  • Conference paper
Experimental Algorithms (SEA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5526))

Included in the following conference series:

Abstract

Well-known measures of presortedness, among others, are the number of inversions needed to sort the input sequence, or the minimal number of blocks of consecutive elements that remain as such in the sorted sequence. In this paper we study the problem of possible composition of measures. For example, after determining the blocks in an input sequence, it is meaningful to measure how many inversions of the blocks are needed to finally sort the sequence. With composite measures in mind we introduce the idea of applying bulk insertions to improve adaptive binary-tree (AVL) sorting; this is done by combining local insertion sort with bulk-insertion methods. We show that bulk-insertion sort is optimally adaptive with respect to the number of bulks and with respect to the number of inversions in the original input. As to composite measures, we define a new measure that tells how many inversions are needed when the extracted bulks form the input. Bulk-insertion sort is shown to be adaptive with respect to this measure. Our experiments show that applying bulk insertion in AVL-tree sorting considerably reduces the number of comparisons and time needed to sort nearly sorted sequences.

This research was partially supported by the Academy of Finland.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Computing Surveys 24(4), 441–476 (1992)

    Article  Google Scholar 

  2. Petersson, O., Moffat, A.: A framework for adaptive sorting. Discrete Applied Mathematics 59(2), 153–179 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Mannila, H.: Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers C-34, 318–325 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  4. Mehlhorn, K.: Sorting presorted files. In: Weihrauch, K. (ed.) GI-TCS 1979. LNCS, vol. 67, pp. 199–212. Springer, Heidelberg (1979)

    Chapter  Google Scholar 

  5. Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. Springer, Heidelberg (1984)

    Book  MATH  Google Scholar 

  6. Tsakalidis, A.K.: AVL-trees for localized search. Information and Control 67, 173–194 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  7. Elmasry, A.: Adaptive sorting with AVL trees. In: IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (IFIP TCS 2004), pp. 307–316. Kluwer, Dordrecht (2004)

    Google Scholar 

  8. Elmasry, A., Fredman, M.L.: Adaptive sorting: an information theoretic perspective. Acta Informatica 45, 33–42 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  9. Soisalon-Soininen, E., Widmayer, P.: Amortized complexity of bulk updates in AVL-trees. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 439–448. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  10. Larsen, K.S.: Relaxed red-black trees with group updates. Acta Informatica 38, 565–586 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  11. Blelloch, G.E., Maggs, B.M., Woo, S.L.M.: Space-efficient finger search on degree-balanced search trees. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 374–383. ACM Press, New York (2003)

    Google Scholar 

  12. Cole, R.: On the dynamic finger conjecture for splay trees, part II: The proof. SIAM Journal on Computing 30(1), 44–85 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  13. Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Informatica 17, 157–184 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  14. Katajainen, J., Levcopoulos, C., Petersson, O.: Local insertion sort revisited. In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol. 401, pp. 239–253. Springer, Heidelberg (1989)

    Chapter  Google Scholar 

  15. Carlsson, S., Levcopoulos, C., Petersson, O.: Sublinear merging and natural mergesort. Algorithmica 9, 629–648 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  16. Moffat, A., Eddy, G., Petersson, O.: Splaysort: Fast, versatile, practical. Software, Practice and Experience 126(7), 781–797 (1996)

    Article  Google Scholar 

  17. Levcopoulos, C., Petersson, O.: Splitsort – an adaptive sorting algorithm. Information Processing Letters 39, 205–211 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  18. Elmasry, A., Hammad, A.: An empirical study for inversions-sensitive sorting algorithms. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 597–601. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  19. Brodal, G.S., Fagerberg, R., Moruz, G.: On the adaptiveness of quicksort. In: 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), Society for Industrial and Applied Mathematics, pp. 130–140 (2005)

    Google Scholar 

  20. Estivill-Castro, V.: Generating nearly sorted sequences – the use of measures of disorder. Electronic Notes in Theoretical Computer Science 91, 56–95 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Helsinki University of Technology, Finland

    Riku Saikkonen & Eljas Soisalon-Soininen

Authors
  1. Riku Saikkonen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eljas Soisalon-Soininen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Fakultät für Informatik, Informatik XI, Technische Universität Dortmund, Otto-Hahn-Straße 14, 44227, Dortmund, Germany

    Jan Vahrenhold

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Saikkonen, R., Soisalon-Soininen, E. (2009). Bulk-Insertion Sort: Towards Composite Measures of Presortedness. In: Vahrenhold, J. (eds) Experimental Algorithms. SEA 2009. Lecture Notes in Computer Science, vol 5526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02011-7_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02011-7_25

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02010-0

  • Online ISBN: 978-3-642-02011-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation